1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;

struct przedzialy	
	{
	long long poczatek;
	long long koniec;
	long long data;	
	long long wysokosc;
	};

stack <przedzialy> stos;
long long t[500005];
long long gdzie[1000005];
long long z[500005];
long long wys[500010];

int main() {
ios_base::sync_with_stdio(0);
long long n,zapytania;
cin>>n>>zapytania;
for(long long i=0;i<n;i++)
	cin>>t[i];
if(n*zapytania>1000000)	
	{//prefiksy
	sort(t,t+n);
	z[0]=t[0];
	for(long long i=1;i<n;i++)
		z[i]=z[i-1]+t[i];
	for(long long i=0;i<1000005;i++)
		gdzie[i]=10000000;//liczba wieksza niz n, nie da sie nic skosic
	for(long long i=n;i>=0;i--)
		{
		gdzie[t[i]-1]=i;	
		}	
	long long ostatni=-1;	
	for(long long i=1000001;i>=0;i--)
		{//cout<<ostatni<<endl;
		if(ostatni!=-1&&gdzie[i]==10000000)
			{
			gdzie[i]=ostatni;
			}
		else
			{
			ostatni=gdzie[i];		
		//	cout<<i<<":"<<ostatni<<" "<<gdzie[i]<<endl;
			}
		}
	/*
	
	cout<<"posortowania tablica"<<endl;
	for(int i=0;i<n;i++)
		cout<<t[i]<<" ";
	cout<<endl;	
	cout<<"tablica gdzie:"<<endl;
	for(int i=0;i<10;i++)//do najwiekszego wzrostu
		{
		cout<<i<<":"<<gdzie[i]<<" ";	
		}
	cout<<endl;
	cout<<"tablica zlicz:"<<endl;
	for(int i=0;i<n;i++)
		{
		cout<<i<<":"<<z[i]<<" ";	
		}
	cout<<endl;*/
	//koniec prefiksow	
	long long d,b;//dzien,wysokosc przyciecia
	stos.push({0,n-1,0,0});//poczatek,koniec,data,wysokosc
	//cout<<stos.top().poczatek<<" "<<stos.top().koniec<<endl;
	while(zapytania--)
		{long long suma=0;
		cin>>d>>b;//dni, wysokosc koszenia
		przedzialy przedzial=stos.top();//zdejmij pierwszy przedzial
		long long iloscdni=d-przedzial.data;
		long long deltawysokosci=b-przedzial.wysokosc;
		long long ilepotrzeba=deltawysokosci/iloscdni; //ile potrzeba wzrostu aby dany ar w przedziale urósł do poziomu koszenia w dana ilosc dni
		if(ilepotrzeba<0)//jesli kosimy nizje niz poprzednio
			ilepotrzeba=0;
	//	cout<<"ile potrzeba "<<ilepotrzeba<<" stos size "<<stos.size()<<endl;
	//	cout<<"gdzie[ilepotrzeba] "<<gdzie[ilepotrzeba]<<" t[poczatek przedzialu] "<<t[przedzial.poczatek]<<endl;
		while(!stos.empty()&&gdzie[ilepotrzeba]<=przedzial.poczatek)//jest musze zaczac kosic wczesniej lub dokladnie ostatni przedzial to zlicz go i usun
			{//cout<<"gdzie[ilepotrzeba] "<<gdzie[ilepotrzeba]<<" poczatek przedzialu"<<przedzial.poczatek<<endl;
		//	cout<<"1 zliczprzedzial od "<<przedzial.poczatek<<" do "<<przedzial.koniec<<" w "<<d-przedzial.data<<" dni i delcie wysokosci koszenia= " <<przedzial.wysokosc-b<<endl;		
			if(przedzial.poczatek!=0)
				suma+=(z[przedzial.koniec]-z[przedzial.poczatek-1])*(d-przedzial.data)+(przedzial.koniec-przedzial.poczatek+1)*(przedzial.wysokosc-b);
			else
				suma+=z[przedzial.koniec]*(d-przedzial.data)+(przedzial.koniec-przedzial.poczatek+1)*(przedzial.wysokosc-b);
			stos.pop();
			if(!stos.empty())
				{
				
				przedzial=stos.top();
				iloscdni=d-przedzial.data;	
				deltawysokosci=b-przedzial.wysokosc;
				ilepotrzeba=deltawysokosci/iloscdni;
				if(ilepotrzeba<0)//jesli kosimy nizje niz poprzednio
					ilepotrzeba=0;
				}
			}
		if(!stos.empty()&&gdzie[ilepotrzeba]>przedzial.poczatek&&gdzie[ilepotrzeba]<=przedzial.koniec)//jesli kosimy w srodku przedzialu,drugi warunek nie spelniony tylko jesli kosimy wyzej niz cokolwiek uroslo
			{//cout<<"gdzie[ilepotrzeba] "<<gdzie[ilepotrzeba]<<" t[poczatek przedzialu] "<<t[przedzial.poczatek]<<endl;
			stos.top().koniec=gdzie[ilepotrzeba]-1;//przesuwam tylko koniec przedzialu
		///	cout<<"3 zliczprzedzial od "<<gdzie[ilepotrzeba]<<" do "<<przedzial.koniec<<" w "<<d-przedzial.data<<" dni i delcie wysokosci koszenia= " <<przedzial.wysokosc-b<<endl;	
			suma+=(z[przedzial.koniec]-z[gdzie[ilepotrzeba]-1])*(d-przedzial.data)+(przedzial.koniec-gdzie[ilepotrzeba]+1)*(przedzial.wysokosc-b);	
		////	cout<<z[przedzial.koniec]-z[gdzie[ilepotrzeba]-1]<<" "<<d-przedzial.data<<" "<<przedzial.koniec-gdzie[ilepotrzeba]+1<<" "<<przedzial.wysokosc-b<<endl;
			}
		if(!stos.empty())	
			{
			przedzial=stos.top();
			if(przedzial.koniec<n-1)	
				stos.push({przedzial.koniec+1 , n-1 , d , b});
			}
		else
			stos.push({0,n-1,d,b});//poczatek,koniec,data,wysokosc	
		cout<<suma<<endl;
		}
	}
else
	{
	long long poprzd=0;
	while(zapytania--)
		{long long d,b;
		cin>>d>>b;
		long long suma=0;
		for(long long i=0;i<n;i++)
			{
			wys[i]+=((d-poprzd)*t[i]);
			//cout<<wys[i]<<" ";
			if(wys[i]>b)
				{
				suma+=wys[i]-b;
				wys[i]=b;	
				}	
			}
		cout<<suma<<endl;;
		
		poprzd=d;	
		}	
	}
return 0;
}