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
#include <stdio.h>
#include <stdlib.h>

#define lint long long // 8 bajtow chocby nie wiem co

//
// jesli kosimy trawe za n-tym razem, to kosimy tylko od pewnego miejsca w prawo
// od tego miejsca w prawo musimy uwzglednic wszystkie koszenia, ktore odbyly sie tam wczesniej, ALE! to kosznie je uniewazni juz...



lint a[500000];
lint last_cut_time[500000];
lint last_cut_height[500000];
int  komplikacji[500000];
lint sum[500001];
lint n,m;


void heapify(lint *a, int i, int n)
{
    int j;
    lint temp;
    temp = a[i];
    j = 2*i;
    while (j <= n) {
        if (j < n && a[j+1] > a[j]) {
            j = j+1;
        } if (temp > a[j]) {
            break;
        } else if (temp <= a[j]) {
            a[j/2] = a[j];
            j = 2*j;
        }
    }
    a[j/2] = temp;
    return;
}

void heapsort(lint *a, int n)
{
    int i;
    lint temp;
    for (i = n; i >= 2; i--) {
        temp = a[i];
        a[i] = a[1];
        a[1] = temp;
        heapify(a, 1, i - 1);
    }
}

void build_heap(lint *a, int n)
{
    int i;
    for(i = n/2; i >= 1; i--) {
        heapify(a, i, n);
    }
}


void przygotuj() {
    int i;
    build_heap(a-1, n);
    heapsort(a-1, n);
    sum[n]=0;
    for(i=n-1;i>=0;i--) {
        last_cut_time[i] = 0;
        last_cut_height[i] = 0;
        sum[i] = sum[i+1] + a[i]; // suma wysokosci na prawo...
        komplikacji[i]= 0;
    }
}



// 1. gdybyśmy trawę kosili zawsze, ale tylko od punktu 0 do wskazanej wysokosci

lint ile_trawy_z_koszenia(
        int pierwszy,  // od tego miejsca
        int ostatni,  // do tego miejsca
        lint wysokosc, // na tej wysokosci 
        lint dzien // tego dnia
        ) {
    int mid = (pierwszy + ostatni) / 2;
    lint ddiff = dzien - last_cut_time[mid];
    lint cursize = last_cut_height[mid] + ddiff * a[mid]; // current size
//    printf("MID = %d %lld %lld \n", mid, last_cut_time[mid], last_cut_height[mid]);
    
    if (pierwszy == ostatni) {
        if (cursize > wysokosc) { 
            last_cut_time[mid] = dzien;
            last_cut_height[mid] = wysokosc;
            return cursize - wysokosc;
        }
        return 0;
    } else {
        if (cursize > wysokosc) { 
            last_cut_time[mid] = dzien;
            last_cut_height[mid] = wysokosc;
            lint here = cursize - wysokosc;
            
            lint prop;
//            if (komplikacji[mid] == 0) {
//                prop = here * (lint)(n-mid) + (sum[mid] - (a[mid] * (lint)(n-mid)) ) - here;
                prop = ile_trawy_z_koszenia(mid+1, ostatni, wysokosc, dzien);
//            komplikacji[mid] = 0;
            
            if (pierwszy < mid) {
                return ile_trawy_z_koszenia(pierwszy, mid-1, wysokosc, dzien) + here + prop;// FORSUJEMY OSTATNIE CIECIE I INNE TAKIE TAM...
            } else {
                return here + prop;
            }
        } else { // cursize < wysokosc - w ogole nas ten kawalek nie interesuje, bo jeszcze do niego nie siegamy...
//            komplikacji[mid]++;
            // jedyny problem polega na tym, ze nie mam dokladnie opisanych czasow koszenia, 
            // tak, żeby je elegancko wyszukiwać
            return ile_trawy_z_koszenia(mid+1, ostatni, wysokosc, dzien);
        }
        
    
    }
}


int main() {
    int i;
    lint d, w;
    scanf("%lld %lld\n", &n, &m); // <= 500 000
    for(i=0;i<n;i++) {
        scanf("%lld", a+i); // <= 10^6
    }
    przygotuj();
    for(i=0;i<m;i++) {
        scanf("%lld %lld\n", &d, &w);
        lint rv = ile_trawy_z_koszenia(0, n-1, w, d);
        printf("%lld\n", rv);
    }
    return 0;
}