Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8. Możesz pobrać ten plik i spróbować otworzyć go samodzielnie. 
  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
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#pragma warning (disable : 4996)

struct event_point
{
	long long day_cut;
	long long height_cut;
	int idx_first_affected;
	event_point(long long d_, long long h_, int i_) : day_cut(d_), height_cut(h_), idx_first_affected(i_) { } ;
};

long long long_long_ceil(long long a, long long b)
{
	return (a+b-1LL) / b;
}


int main(int argc, char* argv[])
{
#ifdef _DEBUG
	freopen("input.txt.extreme_strange_extention", "rt", stdin);
	freopen("output.txt.extreme_strange_extention", "wt", stdout);
#endif
	int N, M;
	scanf("%d %d", &N, &M);
//	cin >> N >> M;
	vector<int> speeds(N);
	for(int i=0; i<N; i++)
//		cin >> speeds[i];
		scanf("%d", &(speeds[i]));
	sort(speeds.begin(), speeds.end());
	vector<long long> speed_sums_till_end(N);
	speed_sums_till_end.back() = (long long)speeds.back();
	for(int i = (int)(speeds.size())-2; i>=0; i--)
		speed_sums_till_end[i] = speed_sums_till_end[i+1] + speeds[i];
	speed_sums_till_end.push_back(0LL);
	vector<event_point> actual_cuts;
	actual_cuts.push_back(event_point(0LL, 0LL, 0));
	long long curr_level;
	long long curr_day;
	long long total_sum_before = 0LL;
	for(int k=0; k<M; k++) {
//		cin >> curr_day >> curr_level;
#ifdef _DEBUG
		scanf("%I64d %I64d", &curr_day, &curr_level);
#else
		scanf("%lld %lld", &curr_day, &curr_level);
#endif
		long long curr_res = 0LL;
		int prev_idx = speeds.size();
		while(!actual_cuts.empty() && actual_cuts.back().height_cut + (curr_day-actual_cuts.back().day_cut) * speeds[actual_cuts.back().idx_first_affected] > curr_level) {
			long long factor1_1 = (speed_sums_till_end[actual_cuts.back().idx_first_affected] - speed_sums_till_end[prev_idx]);
			long long factor1_2 = (curr_day - actual_cuts.back().day_cut);
			long long factor2_1 = (actual_cuts.back().height_cut - curr_level);
			long long factor2_2 = (prev_idx - actual_cuts.back().idx_first_affected);
			long long add1 = factor1_1 * factor1_2;
			long long add2 = factor2_1 * factor2_2;
			curr_res += add1 + add2;
			prev_idx = actual_cuts.back().idx_first_affected;
			actual_cuts.pop_back();
		}
		if(actual_cuts.empty()) {
			actual_cuts.push_back(event_point(curr_day, curr_level, 0));
		} else {
			int curr_idx = upper_bound(
					speeds.begin() + actual_cuts.back().idx_first_affected, 
					speeds.begin() + prev_idx,
					(curr_level - actual_cuts.back().height_cut) / (curr_day - actual_cuts.back().day_cut)
//					long_long_ceil((curr_level - actual_cuts.back().height_cut) , (curr_day - actual_cuts.back().day_cut))
				) - speeds.begin();
			long long factor1_1 = (speed_sums_till_end[curr_idx] - speed_sums_till_end[prev_idx]);
			long long factor1_2 = (curr_day - actual_cuts.back().day_cut);
			long long factor2_1 = (actual_cuts.back().height_cut - curr_level);
			long long factor2_2 = (prev_idx - curr_idx);
			long long add1 = factor1_1 * factor1_2;
			long long add2 = factor2_1 * factor2_2;
			curr_res += add1 + add2;
			if(curr_idx == actual_cuts.back().idx_first_affected) {
				actual_cuts.back().day_cut = curr_day;
				actual_cuts.back().height_cut = curr_level;
			} else { // curr_idx > actual_cuts.back().idx_first_affected, �� ���������
				if(curr_idx < N)
					actual_cuts.push_back(event_point(curr_day, curr_level, curr_idx));
			}
		}
//		cout << curr_res << "\n";
#ifdef _DEBUG
		printf("%I64d\n", curr_res);
#else
		printf("%lld\n", curr_res);
#endif
	}
	return 0;
}