#include <iostream> #include <algorithm> using namespace std; struct wierzcholek{ //wierzcholek drzewa przedzialowego long long int wzrost_razem; int min; int max; long long int niesciete; long long int dni; int ile_razem; bool aktualne; }; long long int rozmiar; long long int *a; wierzcholek * w; long long int zetnij(long long int i, long long int kosiarka, long long int d, bool wyzej_aktualne){ if(w[i].ile_razem==0) return 0; if(w[i].aktualne && w[i].max * (d + w[i].dni) + w[i].niesciete<kosiarka){ w[i].dni+=d; return 0; } if(w[i].aktualne && w[i].min * (d + w[i].dni) + w[i].niesciete>=kosiarka){ long long int zwracane = w[i].ile_razem*(w[i].niesciete-kosiarka) + (w[i].dni+d)*w[i].wzrost_razem; w[i].niesciete=kosiarka; w[i].dni=0; return zwracane; } else if(w[i].min*d>=kosiarka){ if(!wyzej_aktualne) w[i].aktualne=true; w[i].niesciete=kosiarka; return(zetnij(i*2, 0, d, true)+zetnij(i*2+1, 0, d, true)-w[i].ile_razem*w[i].niesciete); } if(w[i].aktualne){ w[i].aktualne=false; w[i*2].aktualne=w[i*2+1].aktualne=true; w[i*2].dni=w[i*2+1].dni=w[i].dni; w[i*2].niesciete=w[i*2+1].niesciete=w[i].niesciete; w[i].dni=0; w[i].niesciete=0; } return (zetnij(i*2, kosiarka, d, false)+zetnij(i*2+1, kosiarka, d, false)); } int main() { ios_base::sync_with_stdio(false); long long int n, m; cin >> n >> m; a=new long long int[n+1]; for(int i=0; i<n; i++) cin >> a[i]; sort(a, a+n); rozmiar=1; while(rozmiar<n) rozmiar*=2; rozmiar *=2; w = new wierzcholek[rozmiar]; for(long long int i=rozmiar/2; i<n+rozmiar/2; i++){ w[i].min=w[i].max=w[i].wzrost_razem=a[i-rozmiar/2]; w[i].ile_razem=1; } for(long long int i=n+rozmiar/2; i<rozmiar; i++){ w[i].ile_razem=0; } for(long long int i=rozmiar/2-1; i>0; i--){ if(!w[i*2].ile_razem){ w[i].ile_razem=0; continue; } if(!w[i*2+1].ile_razem){ w[i].ile_razem=w[i*2].ile_razem; w[i].min=w[i*2].min; w[i].max=w[i*2].max; w[i].wzrost_razem=w[i*2].wzrost_razem; } else{ w[i].ile_razem=w[i*2].ile_razem+w[i*2+1].ile_razem; w[i].min=w[i*2].min; w[i].max=w[i*2+1].max; w[i].wzrost_razem=w[i*2].wzrost_razem+w[i*2+1].wzrost_razem; } } w[1].dni=0; w[1].niesciete=0; w[1].aktualne=true; long long int k, d; long long int ostatnie_koszenie=0; while(m--){ cin >> d; cin >> k; cout << zetnij(1, k, d-ostatnie_koszenie, false) << endl; ostatnie_koszenie=d; } return 0; }
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 | #include <iostream> #include <algorithm> using namespace std; struct wierzcholek{ //wierzcholek drzewa przedzialowego long long int wzrost_razem; int min; int max; long long int niesciete; long long int dni; int ile_razem; bool aktualne; }; long long int rozmiar; long long int *a; wierzcholek * w; long long int zetnij(long long int i, long long int kosiarka, long long int d, bool wyzej_aktualne){ if(w[i].ile_razem==0) return 0; if(w[i].aktualne && w[i].max * (d + w[i].dni) + w[i].niesciete<kosiarka){ w[i].dni+=d; return 0; } if(w[i].aktualne && w[i].min * (d + w[i].dni) + w[i].niesciete>=kosiarka){ long long int zwracane = w[i].ile_razem*(w[i].niesciete-kosiarka) + (w[i].dni+d)*w[i].wzrost_razem; w[i].niesciete=kosiarka; w[i].dni=0; return zwracane; } else if(w[i].min*d>=kosiarka){ if(!wyzej_aktualne) w[i].aktualne=true; w[i].niesciete=kosiarka; return(zetnij(i*2, 0, d, true)+zetnij(i*2+1, 0, d, true)-w[i].ile_razem*w[i].niesciete); } if(w[i].aktualne){ w[i].aktualne=false; w[i*2].aktualne=w[i*2+1].aktualne=true; w[i*2].dni=w[i*2+1].dni=w[i].dni; w[i*2].niesciete=w[i*2+1].niesciete=w[i].niesciete; w[i].dni=0; w[i].niesciete=0; } return (zetnij(i*2, kosiarka, d, false)+zetnij(i*2+1, kosiarka, d, false)); } int main() { ios_base::sync_with_stdio(false); long long int n, m; cin >> n >> m; a=new long long int[n+1]; for(int i=0; i<n; i++) cin >> a[i]; sort(a, a+n); rozmiar=1; while(rozmiar<n) rozmiar*=2; rozmiar *=2; w = new wierzcholek[rozmiar]; for(long long int i=rozmiar/2; i<n+rozmiar/2; i++){ w[i].min=w[i].max=w[i].wzrost_razem=a[i-rozmiar/2]; w[i].ile_razem=1; } for(long long int i=n+rozmiar/2; i<rozmiar; i++){ w[i].ile_razem=0; } for(long long int i=rozmiar/2-1; i>0; i--){ if(!w[i*2].ile_razem){ w[i].ile_razem=0; continue; } if(!w[i*2+1].ile_razem){ w[i].ile_razem=w[i*2].ile_razem; w[i].min=w[i*2].min; w[i].max=w[i*2].max; w[i].wzrost_razem=w[i*2].wzrost_razem; } else{ w[i].ile_razem=w[i*2].ile_razem+w[i*2+1].ile_razem; w[i].min=w[i*2].min; w[i].max=w[i*2+1].max; w[i].wzrost_razem=w[i*2].wzrost_razem+w[i*2+1].wzrost_razem; } } w[1].dni=0; w[1].niesciete=0; w[1].aktualne=true; long long int k, d; long long int ostatnie_koszenie=0; while(m--){ cin >> d; cin >> k; cout << zetnij(1, k, d-ostatnie_koszenie, false) << endl; ostatnie_koszenie=d; } return 0; } |