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

#ifdef PA_LOCAL
#include "../Common/common.h"
#else
#define init(...)
#define finalize()
#endif

using namespace std;

struct Partition
{
	int32_t begin;
	int32_t end;
	int64_t day;
	int64_t height;
};

int main(int argc, const char* argv[])
{
	init("sia_big");

	int32_t types_num, mows_num;
	scanf("%d%d", &types_num, &mows_num);

	int64_t* grass_growths = new int64_t[types_num];
	for (int32_t ti = 0; ti < types_num; ++ti)
	{
		scanf("%lld", &grass_growths[ti]);
	}
	sort(grass_growths, grass_growths + types_num);
	
	int64_t* grass_acc_growths = new int64_t[types_num];
	int64_t acc_growth = 0ll;
	for (int32_t ti = types_num - 1; ti >= 0; --ti)
	{
		acc_growth += grass_growths[ti];
		grass_acc_growths[ti] = acc_growth;
	}
	
	Partition* partitions = new Partition[mows_num + 1];
	
	{
		Partition& part = partitions[0];
		part.begin = 0;
		part.end = types_num;
		part.day = 0ll;
		part.height = 0ll;
	}

	int32_t partitions_num = 1;

	for (int32_t mi = 0; mi < mows_num; ++mi)
	{
		int64_t day, mow_height;
		scanf("%lld%lld", &day, &mow_height);
		
		int64_t grass_mowed = 0ll;

		Partition* part_ptr = lower_bound(partitions, partitions + partitions_num, mow_height,
			[&](const Partition& part, int64_t height)
			{
				return part.height + grass_growths[part.begin] * (day - part.day) < height;
			});

		int32_t new_part_begin = types_num;
		if (part_ptr < partitions + partitions_num)
		{
			new_part_begin = part_ptr->begin;
		}
		
		if (part_ptr > partitions)
		{
			Partition* prev_part_ptr = part_ptr - 1;
			int64_t prev_day_diff = day - prev_part_ptr->day;
			int64_t* prev_growth_ptr = lower_bound(grass_growths + prev_part_ptr->begin, grass_growths + prev_part_ptr->end, mow_height,
				[&](int64_t growth, int64_t height)
				{
					return prev_part_ptr->height + growth * prev_day_diff < height;
				});
			if (prev_growth_ptr < grass_growths + prev_part_ptr->end)
			{
				part_ptr = prev_part_ptr;
				new_part_begin = prev_growth_ptr - grass_growths;
			}
		}

		if (part_ptr < partitions + partitions_num)
		{
			grass_mowed = (part_ptr->height - mow_height) * (part_ptr->end - new_part_begin);
			if (part_ptr->end < types_num)
			{
				grass_mowed += (grass_acc_growths[new_part_begin] - grass_acc_growths[part_ptr->end]) * (day - part_ptr->day);
			}
			else
			{
				grass_mowed += grass_acc_growths[new_part_begin] * (day - part_ptr->day);
			}

			for (int32_t pi = part_ptr - partitions + 1; pi < partitions_num; ++pi)
			{
				Partition& part = partitions[pi];
				grass_mowed += (part.height - mow_height) * (part.end - part.begin);
				if (part.end < types_num)
				{
					grass_mowed += (grass_acc_growths[part.begin] - grass_acc_growths[part.end]) * (day - part.day);
				}
				else
				{
					grass_mowed += grass_acc_growths[part.begin] * (day - part.day);
				}
			}

			if (new_part_begin > part_ptr->begin)
			{
				part_ptr->end = new_part_begin;
				++part_ptr;
			}

			part_ptr->begin = new_part_begin;
			part_ptr->end = types_num;
			part_ptr->day = day;
			part_ptr->height = mow_height;

			partitions_num = part_ptr - partitions + 1;
		}
		
		printf("%lld\n", grass_mowed);
	}

	finalize();
	return 0;
}