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
#include <iostream>
#include <algorithm>
using namespace std;

inline unsigned int lSon(unsigned int i){return 2*i+1;}
inline unsigned int rSon(unsigned int i){return 2*i+2;}
inline unsigned int parent(int i){return (i-1)/2;}

class Node
{
	public:

		unsigned long long addLength;//lastDay
		unsigned long long lastDay; //ostatnie koszenie wszystkiego
		unsigned long long lastTouch; //ostatni dotyk czegos nizej

		unsigned long long lastSum; //dla lastTouch
		unsigned long long min;//dla lastTouch
		unsigned long long max;//dla lastTouch

		unsigned long long growth;//const
		unsigned int leafs; //const
		unsigned int mingr;//const
		unsigned int maxgr;//w sumie const

		Node():
			addLength(0L),
			lastDay(0L),
			lastTouch(0L),
			lastSum(0L),
			growth(0L),
			min(0L),
			max(0L),
			mingr(0),
			maxgr(0),
			leafs(0)
		{}

		long long int Koszenie(unsigned int I,unsigned long long day,unsigned long long length);
} *g_nodes;

long long int Node::Koszenie(unsigned int I,unsigned long long day,unsigned long long length) // I -indeks aktualnego node'a
{
	unsigned long long int result=0L;
	//nasz rodzic zawsze ma aktualne dane dla calego przedzialu jego - niezmiennik, 
	//dla korzenia rodzicem jest on sam, korzen zawsze aktualny
	if(g_nodes[parent(I)].lastDay>lastTouch)//aktualizacja danych dziecka od rodzica
	{
		lastDay=lastTouch=g_nodes[parent(I)].lastDay;
		min=max=addLength=g_nodes[parent(I)].addLength;
		lastSum=leafs*addLength;
	}
	//przeliczenie nowych warosci dla aktualnego dnia
	const unsigned long long int diff=day-lastTouch;
	unsigned long long int locMin=min+diff*mingr;
	unsigned long long int locMax=max+diff*maxgr;

	if(length>=locMax)//nic nie przytniemy
	{
		lastTouch=day;
		lastSum+=growth*diff;
		min=locMin;
		max=locMax;
		result=0L;
	}
	else if(length<=locMin) //wszystko zostanie przycięte
	{
		result = lastSum + diff*growth - length*leafs;
		lastDay=lastTouch=day;
		lastSum=length*leafs;
		addLength=length;
		min=max=length;
	}
	else //nie wszystko ucierpi
	{
		result=g_nodes[lSon(I)].Koszenie(lSon(I),day,length)+g_nodes[rSon(I)].Koszenie(rSon(I),day,length);
		//aktualizacja do synów
		lastTouch=day;
		min=g_nodes[lSon(I)].min;
		max=g_nodes[rSon(I)].max;
		lastSum= g_nodes[lSon(I)].lastSum + g_nodes[rSon(I)].lastSum;
	}
	return result;
}

unsigned int grass[500000];
unsigned long long int days[500000];
unsigned long long int lengths[500000];

int main()
{
	ios_base::sync_with_stdio(0);
	unsigned int arow,skoszen;
	
	unsigned int x;
	cin>>arow>>skoszen;

	g_nodes=new Node[arow*2-1];

	for(int i=0;i<arow;i++)
		cin>>grass[i];
	for(int i=0;i<skoszen;i++)
		cin>>days[i]>>lengths[i];

	std::sort(grass,grass+arow);


	int nearest2pow=1;
	while(nearest2pow<arow)
		nearest2pow<<=1;

	for(int i=0;i<arow;i++)
	{
		int k=arow-1+((nearest2pow+i)%arow); // tylko liscie
		g_nodes[k].growth=g_nodes[k].mingr=g_nodes[k].maxgr=grass[i];
		g_nodes[k].leafs=1;
	}


	for(int i=arow-2;i>=0;i--) //nieliscie w gore
	{
		g_nodes[i].mingr=g_nodes[lSon(i)].mingr;
		g_nodes[i].maxgr=g_nodes[rSon(i)].maxgr;
		g_nodes[i].growth = g_nodes[lSon(i)].growth + g_nodes[rSon(i)].growth;
		g_nodes[i].leafs = g_nodes[lSon(i)].leafs + g_nodes[rSon(i)].leafs;
	}

	for(int i=0;i<skoszen;i++)
		cout<<g_nodes[0].Koszenie(0,days[i],lengths[i])<<"\n";

	delete[] g_nodes;
}