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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int LL;
struct Node{
   LL ilosc=0;
   LL sumaWysokosci=0;
   LL sumaPrzyrostow=0;
   LL minWysokosc=0,maxWysokosc=0;
   LL minPrzyrost=0,maxPrzyrost=0;//for computing minmax wysokosc after growing
   LL deferredSciecie=-1;//if not -1 we want to cut it deferred
   LL ostatnieOdwiedziny=0;//when it should've been cut, to compute przyrost
   Node* left=nullptr;
   Node* right=nullptr;
   void initH(LL h){
      ilosc=1;
      sumaWysokosci=0;
      sumaPrzyrostow = h;
      minWysokosc = maxWysokosc = 0;
      minPrzyrost = maxPrzyrost = h;
   }
   void initParent(Node* l, Node* r){
      left=l;
      right=r;
      sumaPrzyrostow = l->sumaPrzyrostow+r->sumaPrzyrostow;
      ilosc = l->ilosc+r->ilosc;
      sumaWysokosci=0;//at start we can probably assume this
      if(r->sumaPrzyrostow>=0){
         minWysokosc = min(l->minWysokosc,r->minWysokosc);
         minPrzyrost = min(l->minPrzyrost,r->minPrzyrost);
      }else{//if right isn't initalized, we just consider left
         minWysokosc = l->minWysokosc;
         minPrzyrost = l->minPrzyrost;
      }
      maxWysokosc = max(l->maxWysokosc,r->maxWysokosc);
      maxPrzyrost = max(l->maxPrzyrost,r->maxPrzyrost);
   }
   void update(){
      sumaWysokosci = left->sumaWysokosci+right->sumaWysokosci;
      if(right->sumaPrzyrostow>=0){//it's not empty
         minWysokosc = min(left->minWysokosc,right->minWysokosc);
         minPrzyrost = min(left->minPrzyrost,right->minPrzyrost);
      }else{//if right isn't initalized, we just consider left
         minWysokosc = left->minWysokosc;
         minPrzyrost = left->minPrzyrost;
      }
      maxWysokosc = max(left->maxWysokosc,right->maxWysokosc);
      maxPrzyrost = max(left->maxPrzyrost,right->maxPrzyrost);
   }
   void zetnij(LL height){
      //skoro scinamy, tzn. że wszystkie były wyższe, stąd teraz wszystkie są równe height, więc:
      maxWysokosc = height;//min(maxWysokosc,height);
      minWysokosc = height;//min(minWysokosc,height);
      sumaWysokosci = ilosc*height;
   }
   void computePrzyrosty(LL t){
      if(deferredSciecie!=-1){
         zetnij(deferredSciecie);
         if(left!=nullptr){
            left->deferredSciecie = deferredSciecie;
            left->ostatnieOdwiedziny = ostatnieOdwiedziny;
            right->deferredSciecie = deferredSciecie;
            right->ostatnieOdwiedziny = ostatnieOdwiedziny;
         }
         deferredSciecie=-1;
      }
      LL dt = t-ostatnieOdwiedziny;
      minWysokosc+=minPrzyrost*dt;
      maxWysokosc+=maxPrzyrost*dt;
      sumaWysokosci+=sumaPrzyrostow*dt;
      ostatnieOdwiedziny = t;
   }
   LL cut(LL czas, LL scinamyDo){
      computePrzyrosty(czas);
      if(maxWysokosc<=scinamyDo) return 0;
      if(minWysokosc>scinamyDo){
         //scinamy wszystkie
         //mamy aktualną wysokość
         //liczymy przyrost z różnicy
         LL sumaWynikowa = ilosc*scinamyDo;
         minWysokosc = scinamyDo;
         maxWysokosc = scinamyDo;
         LL przyrost = sumaWysokosci-sumaWynikowa;//tyle zostało ścięte
         //prLLf("(%d-%d)\n",sumaWysokosci,sumaWynikowa);
         sumaWysokosci = sumaWynikowa;
         //i zapuszczamy deferred
         if(left!=nullptr){
            left->deferredSciecie=scinamyDo;
            left->ostatnieOdwiedziny=czas;
            right->deferredSciecie=scinamyDo;
            right->ostatnieOdwiedziny=czas;
         }
         return przyrost;
      }else{//partial (on border), so go deeper
         LL l=left->cut(czas,scinamyDo),r=right->cut(czas,scinamyDo);
         //prLLf("{%d+%d}\n",l,r);
         update();
         return l+r;
         //return left->cut(czas,scinamyDo)+right->cut(czas,scinamyDo);
      }
   }
};
vector<Node> drzewo;


int main(){
   LL n,m;
   scanf("%lld%lld",&n,&m);
   vector<LL> pola(n);
   for(LL i=0;i<n;++i){
      scanf("%lld",&pola[i]);
   }
   sort(pola.begin(),pola.end());
   LL potega = 1;
   while(potega<n) potega<<=1;
   drzewo.resize(2*potega+1);
   for(LL i=0;i<n;++i) drzewo[potega+i].initH(pola[i]);
   for(LL i=potega-1;i>=1;--i) drzewo[i].initParent(&drzewo[2*i],&drzewo[2*i+1]);
   Node* root = &drzewo[1];
   for(LL i=0;i<m;++i){
      LL t,h;
      scanf("%lld%lld",&t,&h);
      //prLLf("Suma %d\n",root->sumaWysokosci);
      printf("%lld\n",root->cut(t,h));
   }
}