/* Zadanie: SIA Siano [A] Potyczki Algorytmiczne 2015, runda 1. */ #include <iostream> #include <algorithm> using namespace std; const int nmax=500000+10; typedef long long ll; ll tempo[nmax], ctempo[nmax]; ll d,h,h1, day[nmax], height[nmax]; int start[nmax]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll s; int n,m; cin >>n >>m; //========================================= siejemy for(int i=0; i<n; i++) cin>>tempo[i]; tempo[n]=0; // mech n++; sort(tempo,tempo+n); tempo[n]=0; s=0; for(int i=0; i<=n; i++) ctempo[i]=s+=tempo[i]; //========================================= kosimy int q, a,b, a1; q=0; // mech start[q]=0; day[q]=height[q]=0; q=1; // wykos zerowy, czyli stan po zasianiu start[q]=1; day[q]=height[q]=0; for(int k=0; k<m; k++) { cin >>d >>h; start[q+1]=0; // obrabiamy pełne wykosy s=0; b=n; a1=0; while(q>0) { a = start[q]; h1 = height[q]+(d-day[q])*tempo[a]; if (h1<=h) break; s += (ctempo[b-1]-ctempo[a-1])*(d-day[q]) + (b-a)*height[q] - (b-a)*h; b = a; a1 = a; start[q]=0; q--; } // wykos częściowy if (q) { a = start[q]; h1 = height[q]+(d-day[q])*tempo[b-1]; if(h1>h) { int c,b1=b; // szukamy fragmentu wykosu do skoszenia while ((b1-a)>1) { c=(b1+a)/2; h1 = height[q]+(d-day[q])*tempo[c]; if (h1<=h) a=c; else b1=c; } a++; // a ostatni za niski, więc zwięksamy o +1 if (a<b) { a1=a; s += (ctempo[b-1]-ctempo[a-1])*(d-day[q]) + (b-a)*height[q] - (b-a)*h; } } } if (a1) { q++; height[q] = h; day[q] = d; start[q] = a1; } cout <<s <<'\n'; } }
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 | /* Zadanie: SIA Siano [A] Potyczki Algorytmiczne 2015, runda 1. */ #include <iostream> #include <algorithm> using namespace std; const int nmax=500000+10; typedef long long ll; ll tempo[nmax], ctempo[nmax]; ll d,h,h1, day[nmax], height[nmax]; int start[nmax]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll s; int n,m; cin >>n >>m; //========================================= siejemy for(int i=0; i<n; i++) cin>>tempo[i]; tempo[n]=0; // mech n++; sort(tempo,tempo+n); tempo[n]=0; s=0; for(int i=0; i<=n; i++) ctempo[i]=s+=tempo[i]; //========================================= kosimy int q, a,b, a1; q=0; // mech start[q]=0; day[q]=height[q]=0; q=1; // wykos zerowy, czyli stan po zasianiu start[q]=1; day[q]=height[q]=0; for(int k=0; k<m; k++) { cin >>d >>h; start[q+1]=0; // obrabiamy pełne wykosy s=0; b=n; a1=0; while(q>0) { a = start[q]; h1 = height[q]+(d-day[q])*tempo[a]; if (h1<=h) break; s += (ctempo[b-1]-ctempo[a-1])*(d-day[q]) + (b-a)*height[q] - (b-a)*h; b = a; a1 = a; start[q]=0; q--; } // wykos częściowy if (q) { a = start[q]; h1 = height[q]+(d-day[q])*tempo[b-1]; if(h1>h) { int c,b1=b; // szukamy fragmentu wykosu do skoszenia while ((b1-a)>1) { c=(b1+a)/2; h1 = height[q]+(d-day[q])*tempo[c]; if (h1<=h) a=c; else b1=c; } a++; // a ostatni za niski, więc zwięksamy o +1 if (a<b) { a1=a; s += (ctempo[b-1]-ctempo[a-1])*(d-day[q]) + (b-a)*height[q] - (b-a)*h; } } } if (a1) { q++; height[q] = h; day[q] = d; start[q] = a1; } cout <<s <<'\n'; } } |