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
// Copyright 2015 kajko
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

// in an ascending order
vector<int32_t> growthRate;
vector<int64_t> growthPrefixSum;

struct Range
{
	int32_t begin;  // inclusive
	int32_t end;    // exclusive
};

struct Cut
{
	int64_t h;      // height
	int32_t t;      // timestamp
};

struct Field
{
	Range range;
	Cut lastCut;

	int64_t maxHeightAt(int32_t t) const
	{
		int64_t dt = t - lastCut.t;
		return lastCut.h + dt * growthRate[range.end - 1];
	}

	Field splitAt(int32_t position)
	{
		const Field above {{position, range.end}, lastCut};
		range.end = position;
		return above;
	}

	int64_t yieldFrom(const Cut& cut) const;
};

vector<Field> fields;

int64_t totalGrowthRateAcross(const Range& range)
{
	return growthPrefixSum[range.end] - growthPrefixSum[range.begin];
}

int64_t Field::yieldFrom(const Cut& cut) const
{
	// assumption: all positions in this field are cut by at least 1
	const int64_t dt = cut.t - lastCut.t;
	const int64_t base = range.end - range.begin;
	const int64_t totalVolume = totalGrowthRateAcross(range) * dt + base * lastCut.h;
	return totalVolume - base * cut.h;
}

struct LtCurrentFieldHeight
{
	const int32_t t;
	LtCurrentFieldHeight(int32_t t) : t(t) {}

	bool operator()(const Field& lhs, const Field& rhs) const
	{
		return lhs.maxHeightAt(t) < rhs.maxHeightAt(t);
	}
};

struct LtCurrentPosHeight
{
	const int64_t dt;
	LtCurrentPosHeight(int64_t dt) : dt(dt) {}

	bool operator()(int32_t rateL, int32_t rateR) const
	{
		return (rateL < 0 ? (-rateL) : dt * rateL) < (rateR < 0 ? (-rateR) : dt * rateR);
	}
};

int64_t execute(const Cut& cut, int32_t n)
{

	auto firstField = upper_bound(
		fields.begin(),
		fields.end(),
		Field {{0, 0}, cut},
		LtCurrentFieldHeight(cut.t)
	);

	if (firstField == fields.end()) {
		return 0;
	}

	auto firstAboveCut = upper_bound(
		growthRate.begin() + firstField->range.begin,
		growthRate.begin() + firstField->range.end,
		-max<int64_t>(cut.h - firstField->lastCut.h, 0),
		LtCurrentPosHeight(cut.t - firstField->lastCut.t)
	);
	assert(firstAboveCut != growthRate.end());
	int32_t firstPosition = distance(growthRate.begin(), firstAboveCut);

	int64_t yield = 0;

	for (vector<Field>::iterator it = firstField + 1; it != fields.end(); ++it) {
		yield += it->yieldFrom(cut);
	}

	fields.erase(firstField + 1, fields.end());

	if (firstPosition > firstField->range.begin) {
		fields.push_back(firstField->splitAt(firstPosition));  // this invalidates firstField
		yield += fields.back().yieldFrom(cut);
	}
	else {
		yield += firstField->yieldFrom(cut);
	}

	fields.back().lastCut = cut;
	fields.back().range.end = n + 1;

	return yield;
}

int main()
{
	int32_t n, m;
	cin >> n >> m;
	growthRate.reserve(n + 1);
	growthRate.push_back(0);  // 0th index is unused
	growthPrefixSum.reserve(n + 2);
	growthPrefixSum.push_back(0);

	for (int32_t i = 0; i < n; ++i) {
		int32_t rate = 0;
		cin >> rate;
		growthRate.push_back(rate);
	}
	sort(growthRate.begin(), growthRate.end());

	int64_t s = 0;
	for (int32_t i = 0; i <= n; ++i) {
		s += growthRate[i];
		growthPrefixSum.push_back(s);
	}

	fields.push_back(Field {{1, n + 1}, {0, 0}});
	Cut cut;
	for (int i = 0; i < m; ++i) {
		cin >> cut.t >> cut.h;
		cout << execute(cut, n) << endl;
	}

	return 0;
}