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
#include <cassert>
#include <cstdint>
#include <cstdio>

struct cut_t
{
	int64_t from;
	int64_t day;
	int64_t level;
};

static const int64_t MAX_N = 500 * 1000;
static const int64_t MAX_M = 500 * 1000;
static const int64_t MAX_TEMPO = 1000 * 1000;

static int n, m;

static int64_t temposCount[MAX_TEMPO + 2] = { 0 };
static int64_t aggregatedTempos[MAX_TEMPO + 2];
static int64_t aggregatedCounts[MAX_TEMPO + 2];

static cut_t cutStack[MAX_N + 42];

static inline int64_t getTemposInRange(int begin, int end)
{
	assert(begin <= end);
	return aggregatedTempos[end] - aggregatedTempos[begin];
}

static inline int64_t getCountsInRange(int begin, int end)
{
	assert(begin <= end);
	return aggregatedCounts[end] - aggregatedCounts[begin];
}

static void loadLawn()
{
	// Lawn description
	for (int i = 0; i < n; i++)
	{
		int tempo;
		scanf("%d", &tempo);
		temposCount[tempo] += 1;
	}

	// Precompute counts and tempos
	int64_t accCount = 0;
	int64_t accTempo = 0;
	for (int i = 0; i <= (int)MAX_TEMPO + 1; i++)
	{
		aggregatedTempos[i] = accTempo;
		accTempo += temposCount[i] * (int64_t)i;

		aggregatedCounts[i] = accCount;
		accCount += temposCount[i];
	}

	// for (int i = 0; i < 10; i++)
	// 	printf("%lld ", aggregatedCounts[i]);
	// putchar('\n');

	// for (int i = 0; i < 10; i++)
	// 	printf("%lld ", aggregatedTempos[i]);
	// putchar('\n');
}

static void computeMows()
{
	// Prepare stack
	cut_t * stackTop = cutStack + 1;
	stackTop->from = 0;
	stackTop->day = 0;
	stackTop->level = 0;

	for (int i = 0; i < m; i++)
	{
		int64_t day, level;
		scanf("%lld %lld", &day, &level);
		int64_t harvested = 0;

		int64_t rangeEnd = MAX_TEMPO + 1;

		// printf("\nMowing day #%lld\n", day);

		while (stackTop != cutStack)
		{
			int64_t delay = day - stackTop->day;
			int64_t maxGrowth = level - stackTop->level;

			// printf("delay: %lld\n", delay);
			// printf("maxGrowth: %lld\n", maxGrowth);

			// Check if mowing cuts grass from this range
			if (delay * (rangeEnd - 1) > maxGrowth)
			{
				int64_t harvestStart;
				if (delay * stackTop->from > maxGrowth)
					harvestStart = stackTop->from; // Cut whole range
				else
					harvestStart = maxGrowth / delay + 1; // TODO: Check

				// printf("harvestStart: %lld\n", harvestStart);
				// assert(stackTop->from <= harvestStart && harvestStart <= rangeEnd);

				int64_t delayFactor = delay * getTemposInRange(harvestStart, rangeEnd);
				int64_t levelFactor = maxGrowth * getCountsInRange(harvestStart, rangeEnd);

				harvested += delayFactor;
				harvested -= levelFactor;

				// printf("D: %lld, L: %lld\n", delayFactor, levelFactor);
				// printf("Havested from (%lld, %lld)\n", harvestStart, rangeEnd);
				rangeEnd = harvestStart;

				// If we cut a complete range, pop it from the stack
				if (stackTop->from == harvestStart)
				{
					stackTop--;
					// puts("Popping");
				}
				// else
					// puts("Not popping");
			}
			else
				break;
		}

		// Put a filling range on top
		stackTop++;
		stackTop->from = rangeEnd;
		stackTop->day = day;
		stackTop->level = level;
		// printf("Put cap at %lld\n", rangeEnd);

		// Print result
		printf("%lld\n", harvested);
	}
}

int main()
{
	scanf("%d %d", &n, &m);

	loadLawn();
	computeMows();

	return 0;
}