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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include<stdlib.h>
#include<stdio.h>

class Node;

int* speed;     //!< czas przyrostu jednodniowy dla i-tej odmiany
int64_t* grow;      //!< jednodniowy przyrost dla wszystkich od i-tego
Node* start;	//!< początek listy
Node* end;      //!< koniec listy
int memPos=0;
Node* mem;      //!< Pomocnicza pamięc na obiekty, aby nie było dużo allokacji

#ifdef DEBUG
#define ASSERT(cond, msg) if(!(cond)) throw msg
#else
#define ASSERT(cond, msg)
#endif

#ifdef DEBUG
#define log(format, ...)     printf(format "\n", __VA_ARGS__)
#else
#define log(...)
#endif

/**
 * List dwukierunkowa
 */
class Node {
public:
	int i;  //!< odmiana
	int64_t h;  //!< wysokość ostatniego podcięcia
	int64_t d;  //!< czas ostatniego podcięcia
	Node* prev; //!< poprzedni w liście
	Node* next; //!< następny w liście
public:
    Node() {}

	inline void init(int _i, int64_t _h, int64_t _d) { i=_i; h=_h; d=_d; prev=NULL; next=NULL; }

	/// funkcja wyliczajaca wysokosc trawy danej odmiany będącej w danym zakresie ( this.i<=kind<next.i
	inline int64_t height(int64_t now, int kind) {
		// now>d bo kolejne podciecia sa w kolejnych dniach
        ASSERT(d<now,"Illegal now day!");
        ASSERT(kind>=i && kind<next->i,"Kind out of index!");
		int64_t res=h+(now-d)*(int64_t)speed[kind];	// wysokosc ostatniego odciecia + (liczba dni od ostatniego odciecia * predkosc rosniecia)
		log("Day=%lld, I=%d, Height=%lld",now,kind,res);
		return res;
		// wynik miesci sie w int (2^31), bo nigdy nie ma byc sytuacji, aby trawa miala wysokosc przekraczajaca 10^12.
	}

	/**
	  * Funkcja zwracająca ilość przyciętą dla zadanych parametrów dla zadanego fragmentu
	  * Dodatkowo funkcja aktualizuje fragment do zadanego przycięcia
	  */
	inline int64_t cut(int64_t day, int64_t theight) {
        ASSERT(day>d,"Illegal day");
        ASSERT(height(day,i)>=theight,"Illegal command state!");
        int64_t dif=day-d;  // roznica w dniach od ostatniego podciecia na tym fragmencie
        int len=next->i - i;    // długość fragmentu (ilość odmian/arów).
        int64_t dayGrow=grow[i]-grow[next->i];  // przyrost danego fragmentu w ciągu jednego dnia
        int64_t total=h*len + dayGrow*dif;      // w sumie jest to ilość, która pozostała w ostatniego podcięcia + to ile urosło (dzienny przyrost * ilość od przycięcia)
        int64_t res=total-(len*theight);      // ilość ścięta, to ilość całkowita pomniejszona o to co pozostało
        log("Cut Day=%lld, Height=%lld, At=%d, Res=%lld",day,theight, i, res);

        d=day;  // aktualizujemy dzien przycięcia
        h=theight;   // oraz wysokość przycięcia

        return res;
	}

	/**
	 * Funkcja łącząca fragment z następnymi. Po przycinaniu każdy kolejny element jest zrównany do tej samej wysokości
	 * bo musiałbyć wyższy ze względu na kolejność.
	 */
	void merge() {
        if(next==end) return; // ostatni element to "terminator" i on nie jest uwzględniany w łączeniu
        log("Merge %lld + %lld",i, next->i);
        Node *tmp=next;
        next=tmp->next; next->prev=this;    // aktualizujemy połączenia pomiędzy elementami
        //delete tmp; // usywamy nieużywany element listy
	}

	/**
	 * Funkcja szukająca punktu podziału metodą bisekcji.
	 * Zwracany jest najmniejszy punkt, dla którego wysokość jest większa lub równa height z parametru
	 */
	int find(int64_t day, int64_t theight, int left, int right) {
        //log("Find: Day=%d, Height=%d, Left=%d, Right=%d\n",day,theight, left, right);
        if(left>right) {
            if(height(day, right)<theight) return left;
            return right;
        }
        ASSERT(left>=i && right<next->i, "Invalid search range!");
        int c=left+((right-left)/2);
        int64_t mh=height(day,c);
        if(mh<theight) {
            return find(day, theight, c+1, right);
        } else {
            return find(day, theight, left, c-1);
        }
	}

	/**
	 * Metoda dzieląca fragment na dwa - obecny jest przycinany i wstaiwany jest przed dany (dzielony) element
	 */
	void split(int pos) {
        ASSERT(pos>i && pos<next->i,"Invalid split point!");
        Node* n=&mem[memPos++];
        n->init(i,h,d);
        log("Split: %d",pos);
        if(prev==NULL) {
            start=n;
            n->next=this;
            prev=n;
        } else {
            prev->next=n; n->next=this;
            n->prev=prev; prev=n;
        }
        i=pos;  // i nowa pozycja podzialu
	}
};

/**
 * Funkcja przetwarzająca kolejne zapytanie i zwracająca wynik
 */
int64_t process(int64_t day, int64_t height) {
    log("Processing query: %lld %lld",day,height);
    int64_t sum=0;
    Node *p=end->prev;  // end-a nie przetwarzamy, bo jest tylko terminatorem
    for(;;) {

        if(p->height(day,p->i)>=height) {   // jeżeli początek fragmentu jest odpowiednio wysoki, to znaczy, że reszta fragmentu również spełnia ten warunek i moża ją zaliczyć
            sum+=p->cut(day,height);
            p->merge(); // łączymy z kolejnymi
            ASSERT(p->next==end,"Invalid state!");
            if(p==start) break; // to już początek, nie ma sensu iść i możliwości iść dalej
            p=p->prev;      // przechodzimy do kolejnego fragmentu
        } else {        // jeżeli początek fragmentu jest niższej wartości, to może trzeba będzie podzielić fragment
            if(p->height(day,p->next->i-1)<=height) break;  // cały fragment jest niższej wysokości, więc dalej nie ma sensu analzować
            // fragment należy podzielić i tym samym znaleźć pozycję podziału
            int left=p->i;
            int right=p->next->i-1;
            int sp=p->find(day, height, left, right);
            log("Search Day=%lld, Height=%lld, Res=%lld", day, height, sp);
            ASSERT(p->height(day,sp)>=height && p->height(day,sp-1)<height, "Invalid split point found!");
            p->split(sp);

            ASSERT(p->i==sp && p->prev->i==left && p->next->i==right+1,"Invalid split result!");
            // i wykonujemy kolejną iterację na tym samym fragmencie, bo będzie obsłużony przez pierwszy warunek
        }
    }
    return sum;
}

/**
 * Zwykłą funkcja do porównania int-w na potrzeby qsort
 */
int cmp(const void* v1, const void* v2) {
	return (*((int*)v1))-(*((int*)v2));
}

int main(int argc, char** argv) {
	int n,m;

	scanf("%d %d",&n,&m);
	speed=(int*)malloc(sizeof(int)*(n+1));
	for(int i=0;i<n;++i) {
		scanf("%d",&speed[i]);
	}
	speed[n]=0;
	qsort(speed,n,sizeof(int),cmp);
#ifdef DEBUG
	printf("Sorted: ");
	for(int i=0;i<n;++i) printf("%d ",speed[i]);
	printf("\n");
#endif
	// tablica z dziennym przyrostem wszystkich trwa, ktore przynajmniej tak szybko jak i-ta (posortowane)
	grow=(int64_t*)malloc(sizeof(int64_t)*(n+1));
	grow[n]=0;
	for(int i=n-1;i>=0;--i) {
		grow[i]=grow[i+1]+speed[i];
	}
#ifdef DEBUG
	printf("Grow: ");
	for(int i=0;i<n;++i) printf("%d ",grow[i]);
	printf("\n");
#endif
    mem=(Node*)malloc(sizeof(Node)*(m+4));
    start=&mem[memPos++];
    end=&mem[memPos++];
    start->init(0,0,0);  // początkowy element - wskazuje na początek i ma zerowe wartości
    end->init(n,0,0);    // ostatni element - jest pomocniczy - terminator listy i wskazuje na element n-ty, czyli poza danymi
    start->next=end; end->prev=start;   // łączymy elementy listy
	for(int i=0;i<m;++i) {
		int64_t day, height;
		scanf("%lld %lld",&day,&height);
		printf("%lld\n",process(day, height));
	}

	return 0;
}