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
/*
Tomasz Stepanko
PA2015 Runda1 
Zadanie A - siano
*/
#include <stdio.h>
#include <algorithm>
#include <math.h>

bool compare (int i,int j) { return (i>j); }

int main()
{
	int n,m;
	scanf("%d %d", &n, &m);
	int* grassGrowthFactor = new int[n];
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &grassGrowthFactor[i]);
	}
	long long* day = new long long[m + 1];
	day[0] = 0;
	long long* hight = new long long[m];
	for(int i = 0; i < m; i++)
	{
		scanf("%d %d", &day[i + 1], &hight[i]);
	}
	
	long long* grass = new long long[n];
	for(int i = 0; i < n; i++)
	{
		grass[i] = 0;
	}
	
	// case for small main
	if(m > log2((double)n))
	{
		for(int i = 0; i < m; i++)
		{
			long long sum = 0;
			for(int j = 0; j < n; j++)
			{
				grass[j] += grassGrowthFactor[j]*(day[i + 1] - day[i]);
				if(grass[j] > hight[i])
				{
					sum += grass[j] - hight[i];
					grass[j] = hight[i];
				}
			}
			printf("%lld\n", sum);
		}
	}
	else
	{
		std::sort(grassGrowthFactor, grassGrowthFactor+n, compare);
		long long* lastDay = new long long[n];
		for(int i = 0; i < n; i++)
		{
			lastDay[i] = 0;
		}
		for(int i = 0; i < m; i++)
		{
			long long sum = 0;
			for(int j = 0; j < n; j++)
			{
				// the last day for each place has to be stored somwere as not every place is updated
				grass[j] += grassGrowthFactor[j]*(day[i + 1] - lastDay[j]);
				lastDay[j] = day[i+1];
				if(grass[j] <= hight[i])
				{					
					break;
				}
				sum += grass[j] - hight[i];
				grass[j] = hight[i];
			}
			printf("%lld\n", sum);
		}
	}
	return 0;
}