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
/* Marcin 'Gregor' Gregorczyk
 * PA 2015, runda 1, zadanie Siano */

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef unsigned long long LL;

struct mark {
  LL position;
  LL day;
  LL height;
};

inline bool cmp(const mark& a, const mark& b) {
  return a.position < b.position;
}

int n, m;
vector<LL> heights;
vector<LL> sufix;
vector<mark> marks;

LL getResult(LL day, LL height);

LL prevDay(int index) {
  mark tmp; tmp.position = index;
  vector<mark>::iterator it = upper_bound(marks.begin(), marks.end(), tmp, cmp);
  return (*(--it)).day;
}

LL prevHeight(int index) {
  mark tmp; tmp.position = index;
  vector<mark>::iterator it = upper_bound(marks.begin(), marks.end(), tmp, cmp);
  return (*(--it)).height;
}

int findSufix(LL day, LL height) {
  int beg = 0, end = n;
  while(beg < end) {
    int mid = (beg + end) / 2;
    if(heights[mid] * (day - prevDay(mid)) + prevHeight(mid) < height)
      beg = mid+1;
    else end = mid;
  }
  return beg;
}

int main() {
  LL day, height;
  scanf("%d%d", &n, &m);
  
  heights.resize(n);
  sufix.resize(n+1);
  mark tmp; tmp.position = 0; tmp.height = 0; tmp.day = 0;
  marks.push_back(tmp);  

  for(int i = 0; i < n; i++)
    scanf("%llu", &heights[i]);

  sort(heights.begin(), heights.end());
  
  for(int i = n-1; i >= 0; i--)
    sufix[i] = sufix[i+1] + heights[i];
  
  for(int i = 0; i < m; i++) {
    scanf("%llu%llu", &day, &height);
    printf("%llu\n", getResult(day, height));
  }

  return 0;
}

LL getResult(LL day, LL height) {
  int beg = findSufix(day, height);
  int end = n;
  LL result = 0;

  while(!marks.empty() && marks.back().position >= beg) {
    result += (end-marks.back().position) * marks.back().height + (day - marks.back().day) * (sufix[marks.back().position]-sufix[end]) - (end-marks.back().position)*height;
    end = marks.back().position;
    marks.pop_back();
  }
  if(end > beg) result += (end-beg) * marks.back().height + (day - marks.back().day) * (sufix[beg]-sufix[end]) - (end-beg)*height;
  if(beg < n) {
    mark tmp;
    tmp.day = day; tmp.position = beg; tmp.height = height;
    marks.push_back(tmp);
  }
  return result;
}