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
#include <stdio.h>

#define N_MAX 500000
#define M_MAX 500000
#define MAX_A 1000000
unsigned int 	M,	// Ilość koszeń (1.. 500*10^3)
	 N, Nn;	// Ilość zasiewów (1..500*10^3)
unsigned int A[MAX_A+1];	// Wartości (1..10^6)
unsigned int Aw[N_MAX];
unsigned long long d[M_MAX];	// Wartości (1..10^12)
long long b[M_MAX];   // Wartości (0..10^12)
long long w[N_MAX];  // Wysokości trawy (0..10^12) 

int main()
{
	int i, j, val;
	long long  last, deltaD, prevB;
	scanf("%d %d", &N, &M);
	for(i = 0; i < N; i++)	
	{
		scanf ("%d", &val);
		w[i] = 0;
		A[val] ++;
	}
	j = 0;
	for(i = 0; i <= MAX_A ; i++)
	{
		if(A[i] >0)
		{
			Aw[j] = i;
			A[j++] = A[i];
		}	
	}
	Nn = j;
	fprintf(stderr, "N=%d Nn=%d\n", N, Nn);	
	scanf("%lld %lld", d, b);
	last = d[0];
	for (i= 1; i < M;i++) 
	{
		scanf("%lld %lld", d+i, b+i);
		d[i] -= last;	// wpisujeny różnicę pomiędzy koszeniami
		last += d[i];		
	}
	prevB = 0;
	deltaD = 0;
	for(i = 0; i < M; i++)
	{
		unsigned long long sum ;
		
		sum = 0;
		deltaD += d[i];	
		if( b[i] - prevB < deltaD*Aw[Nn-1]) 
		{		
			for(j = 0; j < Nn; j++)
			{
				w[j] += deltaD*Aw[j];
				if(w[j] > b[i])
				{
					sum += A[j]*(w[j] - b[i]);
					w[j] = b[i];	
				}
			}
			prevB = b[i];
			deltaD = 0;
		}
		printf("%lld\n", sum);
	}
	return 0;
}