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<cstdio>
#include<algorithm>
#include<vector>
#include<cassert>
using namespace std;

#define MAX_SPEED 1000001ll
#define MAX_HEIGHT 1000000000001ll

#define deb(a)


vector<long long> speeds;
long long suffix_sum[501000];

struct event {
  long long day;
  long long height;
  long long position;

  event(long long p, long long h, long long t) : day(t), height(h), position(p) {}
};

struct events_comparator {
  long long day;

  events_comparator(long long d) : day(d) {}
  bool operator()(event ev, long long height) {
    // looking for first greater!
    deb(printf("events_comparator(at %lld) %lld >= %lld\n", ev.position, speeds[ev.position] * (day - ev.day) + ev.height, height));
    return speeds[ev.position] * (day - ev.day) + ev.height < height;    
  }
};

struct speed_comparator {
  long long day_difference;
  long long base_height;
  speed_comparator(long long h, long long d) : day_difference(d), base_height(h) {}
  bool operator()(long long speed, long long height) {
    deb(printf("speed_comparator(at %lld, dd: %lld) %lld >= %lld\n", speed, day_difference, speed * day_difference + base_height, height));
    return speed * day_difference + base_height < height;
  }
};

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

  for (int i = 0; i < n; i++) {
    int speed;
    scanf("%d", &speed);
    speeds.push_back(speed);
  }

  sort(speeds.begin(), speeds.end());

  deb(for (int i = 0; i < n; i++) printf("%lld ", speeds[i]); printf("\n"));

  suffix_sum[speeds.size()] = 0;

  for (int i = speeds.size() -1; i >= 0; i--) {
    suffix_sum[i] = suffix_sum[i+1] + speeds[i];
  }

  deb(for (int i = 0; i <= n; i++) printf("%lld ", suffix_sum[i]); printf("\n"));

  speeds.push_back(MAX_SPEED);

  vector<event> events;
  events.push_back(event(0,0,0)); // at time 0, from position = 0 to end, height was 0
  events.push_back(event(n,MAX_HEIGHT,0)); // guard for binary search! 

  for (int i = 0; i < m; i++) {
    long long day, height;

    scanf("%lld%lld", &day, &height);
    deb(printf("cutting: %d, day=%lld, height=%lld\n", i, day, height));

    vector<event>::iterator first_greater_event = lower_bound(events.begin(), events.end(), height, events_comparator(day));
    deb(printf("first_greater_event: %ld\n", first_greater_event - events.begin()));
    assert(first_greater_event != events.end()); // if nothing, guard should be found!


    vector<long long>::iterator cut_start_it;
    if (first_greater_event == events.begin()) {
      cut_start_it = speeds.begin();
      assert(first_greater_event->position == 0);
    } else {
      int right_end = first_greater_event->position;
      vector<event>::iterator prev_event = first_greater_event - 1;
      deb(printf("searching [0, %d] cur day: %lld, prev_day: %lld\n", right_end, day, prev_event->day));
      cut_start_it = lower_bound(speeds.begin(), speeds.begin() + right_end, height,
                                 speed_comparator(prev_event->height,  day - prev_event->day));
    }
    assert(cut_start_it != speeds.end());

    deb(printf("cutting starts at: %ld\n", cut_start_it - speeds.begin()));
    // TODO: maybe check whether cut_start_it is valid 

    int cut_start_position = cut_start_it - speeds.begin();

    int last_event_position = n;

    long long cut_sum = 0;
    while (!events.empty() && events.rbegin() -> position >= cut_start_position) {
      // include to sum
      long long width = last_event_position - events.rbegin()->position;
      long long speed = -(suffix_sum[last_event_position] - suffix_sum[events.rbegin()->position]);
      long long duration = day - events.rbegin()->day; 

      long long grown = speed*duration;
      long long cutDifference = width * (events.rbegin()->height - height);

      long long partAmount = grown + cutDifference;

      cut_sum += partAmount;

      deb(printf("for [%d,%lld] grown = %lld, cutDifference = %lld, cutAmount = %lld, cumSum: %lld\n", last_event_position, events.rbegin()->position, grown, cutDifference, partAmount, cut_sum));

      // removing old events!
      last_event_position = events.rbegin()->position;
      events.pop_back();
    }

    if (!events.empty()) {
      long long width = last_event_position - cut_start_position; 
      long long speed = -(suffix_sum[last_event_position] - suffix_sum[cut_start_position]);
      long long duration = day - events.rbegin()->day; 

      long long grown = speed*duration;
      long long cutDifference = width * (events.rbegin()->height - height);

      long long partAmount = grown + cutDifference;

      cut_sum += partAmount;
      deb(printf("(last) for [%d,%d] grown = %lld, cutDifference = %lld, cutAmount = %lld, cumSum: %lld\n", last_event_position, cut_start_position, grown, cutDifference, partAmount, cut_sum));
    }

    events.push_back(event(cut_start_position,height,day)); // add a new event
    events.push_back(event(n,MAX_HEIGHT,day)); // add guard!

    printf("%lld\n", cut_sum);


  }


}