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
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
162
163
164
165
166
#include <cstdio>
#include <algorithm>
#include <iostream>

//#define DBG
//#define TEST

using namespace std;

struct Koszenie {
  long long d;  // numer dnia
  long long b;  // wysoko�� koszenia
  int c;  // ostatni numer skoszonej trawy (najwolniejsza trawa skoszona w tym koszeniu)
};

bool cmp(int a, int b) {return a > b;}

int n, m, *a;
long long *b, *d;


/////////////////////////////////////////////////////////////////////////////////////////////

void licz(long long *twyn)
{
  int i;
  long long *sa = new long long[n + 1];  //sa[i] = sum(a[0]..a[i-1])
                                         //sa[j + 1] - sa[i] = sum(a[i]..a[j]) dla j >= i
  #define SUMA(i, j) (sa[j + 1] - sa[i])
  #define ILE(i, j)  (j - i + 1)

  sort(a, a + n, cmp);  // sortowanie traw malej�co
  sa[0] = 0;
  for (i = 0; i < n; ++i) sa[i + 1] = sa[i] + a[i];

  Koszenie *K = new Koszenie[m];  // K[i] dane kolejnego koszenia wg rosn�cego c i d
  int ik = -1; // ostatni element wype�niony w K

  for (i = 0; i < m; ++i) {
    #ifdef DBG
    printf("i=%d\n", i);
    #endif
    long long wyn = 0;
    int c0 = 0; // najszybsza trawa kt�ra jest w analizowanym fragmencie
    // je�li ci�cie jest poni�ej lub r�wno wysoko�ci do kt�rej uros�a najwolniejsza trawa skoszona w danym koszeniu
    // od tamtego dnia to ca�y fragment jest r�wno ci�ty, a punkt graniczny b�dzie gdzie� dalej
    // albo dok�adnie na granicy jak kolejna jest ju� za niska do ci�cia

    while (ik >= 0 && b[i] <= K[ik].b + (d[i] - K[ik].d) * a[K[ik].c]) {
      #ifdef DBG
      long long tmp = SUMA(c0, K[ik].c) * (d[i] - K[ik].d) - ILE(c0, K[ik].c) * (b[i] - K[ik].b);
      printf("   %I64d * (%I64d - %I64d) - %d * (%I64d - %I64d) = %I64d\n",
             SUMA(c0, K[ik].c), d[i], K[ik].d, ILE(c0, K[ik].c), b[i], K[ik].b, tmp);
      wyn += tmp;
      printf("   fragment ik=%d, c0=%d, K[ik].c=%d siano=%I64d wyn=%I64d\n", ik, c0, K[ik].c, tmp, wyn);
      #else

      wyn += SUMA(c0, K[ik].c) * (d[i] - K[ik].d) // wszystko co uros�o w tym segmencie od ostatniego koszenia
          -  ILE(c0, K[ik].c) * (b[i] - K[ik].b); // ile zostaje bo tniemy wy�ej ni� poprzednio
      #endif
      c0 = K[ik].c + 1;
      ik--;
    }
    // UWAGA: co je�li ci�cie by�o na najwolniejszej trawie?   --> patrz (**)
    // UWAGA: co je�li nic si� nie zetnie bo ci�cie za wysoko? b�dzie dobrze bo znajdzie si� skrajny lewy i warunek
    //        sprawdzi, �e nie ci�� (ale mo�naby to if-em normalnym obs�u�y� bez tego b-searcha)


    // znale�� c = miejsce ci�cia w znalezionym fragmencie c0..c1
    int c1; // najwolniejsza trawa w fragmencie, o kt�rej wiadomo, �e �adna wolniejsza nie jest ci�ta
    long long b1; // wysoko�� ostatniego ci�cia trawy c1
    long long d1; // dzie� ostatniego ci�cia trawy c1

    if (ik == -1) { // trzeba sprawdzi� fragment do ko�ca - przypadek, �e najwolniejsza trawa nigdy nie by�a ci�ta (**)
      c1 = n - 1;
      b1 = 0;
      d1 = 0;
    }
    else {
      c1 = K[ik].c;
      b1 = K[ik].b; // wysoko�� ostatniego ci�cia najwolniejszej trawy we fragmencie
      d1 = K[ik].d;
    }

    #ifdef DBG
    printf("   ik=%d, c0=%d, c1=%d, b1=%I64d, d1=%I64d, wyn=%I64d\n", ik, c0, c1, b1, d1, wyn);
    #endif

    // wysoko�� trawy c (=c0..c1) to b1 + (d - d1) * a[c]
    // trzeba znale�� najwi�ksze c, t.�e b1 + (d - d1) * a[c] >= b
    int c;
    int lewy = c0, prawy = c1;
    while (prawy > lewy) {
      int srodek = (lewy + prawy + 1) / 2;
      if (b1 + (d[i] - d1) * a[srodek] >= b[i])
        lewy = srodek;
      else
        prawy = srodek - 1;
    }
    #ifdef DBG
    printf("   lewy=%d, prawy=%d\n", lewy, prawy);
    #endif
    c = lewy;

    if (c0 <= c1 && // je�li statnie ci�cie w p�tli by�o do najwolniejszej trawy to tu ju� nie ma co ci��
        b1 + (d[i] - d1) * a[c] >= b[i]) {
      #ifdef DBG
      long long tmp = SUMA(c0, c) * (d[i] - d1)  // wszystko co uros�o od ostatniego koszenia
          -  ILE(c0, c) * (b[i] - b1);  // ile zostaje bo tniemy wy�ej ni� poprzednio
      printf("   tniemy reszte do %d siano=%I64d\n", c, tmp);
      #endif

      // by�o ci�cie - doliczy� ilo�� �ci�tej trawy od c0 do c
      wyn += SUMA(c0, c) * (d[i] - d1)  // wszystko co uros�o od ostatniego koszenia
          -  ILE(c0, c) * (b[i] - b1);  // ile zostaje bo tniemy wy�ej ni� poprzednio

      ik++;     // od�o�y� ostatnie ci�cie na K
      K[ik].d = d[i];
      K[ik].b = b[i];
      K[ik].c = c;
    }
    else {
      if (c0 > 0) {
        // by�o ci�cie w p�tli - trzeba je od�o�y� do K skoro nie by�o potem ci�cia w �rodku fragmentu lub na ko�cu
        ik++;
        K[ik].d = d[i];
        K[ik].b = b[i];
        K[ik].c = c0 - 1;
      }
    }
    #ifdef DBG
    for(int q = 0; q <= ik; ++q) printf("     %d (c=%d, d=%I64d, b=%I64d)\n", q, K[q].c, K[q].d, K[q].b);
    printf("   teraz jest=%I64d\n", wyn);
    #endif

    twyn[i] = wyn;
  }
  delete K;
}

#ifdef TEST
#include "sia_test.h"
#endif // TEST

int main() {
  ios_base::sync_with_stdio(false);

#ifdef TEST
  test();
  return 0;
#endif // TEST

  int i = 0;
  scanf("%d%d", &n, &m);
  a = new int[n];
  b = new long long[m];
  d = new long long[m];
  long long *wyn = new long long[m];
  for (i = 0; i < n; ++i) scanf("%d", a + i);
  for (i = 0; i < m; ++i) scanf("%lld%lld", d + i, b + i);
  licz(wyn);
  for (i = 0; i < m; ++i) printf("%lld\n", wyn[i]);


  return 0;
}