8293: BZOJ4293:[PA2015]Siano
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
农夫Byteasar买了一片n亩的土地,他要在这上面种草。 他在每一亩土地上都种植了一种独一无二的草,其中,第i亩土地的草每天会长高a[i]厘米。 Byteasar一共会进行m次收割,其中第i次收割在第d[i]天,并把所有高度大于等于b[i]的部分全部割去。Byteasar想知道,每次收割得到的草的高度总和是多少,你能帮帮他吗?
输入格式
第一行包含两个正整数n,m(1<=n,m<=500000),分别表示亩数和收割次数。 第二行包含n个正整数,其中第i个数为a[i](1<=a[i]<=1000000),依次表示每亩种植的草的生长能力。 接下来m行,每行包含两个正整数d[i],b[i](1<=d[i]<=10^12,0<=b[i]<=10^12),依次描述每次收割。 数据保证d[1]<d[2]<...<d[m],并且任何时刻没有任何一亩草的高度超过10^12。
输出格式
输出m行,每行一个整数,依次回答每次收割能得到的草的高度总和。
样例输入
4 4 1 2 4 3 1 1 2 2 3 0 4 4
样例输出
6 6 18 0
提示
第1天,草的高度分别为1,2,4,3,收割后变为1,1,1,1。 第2天,草的高度分别为2,3,5,4,收割后变为2,2,2,2。 第3天,草的高度分别为3,4,6,5,收割后变为0,0,0,0。 第4天,草的高度分别为1,2,4,3,收割后变为1,2,4,3。
题目来源
By Claris