/* * File: main.cpp * Author: luk * * Created on 29 wrzesień 2015, 19:06 */ #include <cstdlib> #include <iostream> using namespace std; #define MILION 1000000 #define POL 500000 long long int sufit(double x){ if(x<0)return 0; long long int y=x; if(x>y)return y+1; else return y; } int a[500005]; long long int sa[500005]; int ile_a[1000005]; int ma[1000005]; long long int td[500005]; // dzien koszenia tarasu long long int tb[500005]; // wysokosc koszenia tarasu int tp[500005]; // poczatek tarasu int main() { // LONG LONG INT - tam gdzie trzeba !!!!!! int n,m; // n - ile pól, m-ile koszen long long int i,j,k,dzien,kosz,b,ti,a_odc,i_odc; long long int kg; cin >> n; cin >> m; for(i=1;i<=n;i++) cin >> a[i]; for(i=0;i<=MILION;i++) ile_a[i]=0; for(i=1;i<=n;i++) ile_a[ a[i] ] ++; k=1; for(i=0;i<=MILION;i++){ ma[i]=k; // pierwsze wystapienie ???? spr gdy nie ma ??? for(j=1;j<=ile_a[i];j++){ // uzupelnienie tablicy a w kolejnosci a[k]=i; k++; } } sa[0]=0; for(i=1;i<=n;i++) sa[i]=sa[i-1]+a[i]; // skumulowane wysokosci td[0]=0; tb[0]=0; tp[0]=1; ti=0; // zerowe zasianie, ti - nr najwyzszego tarasu int tn=0; for(kosz=1;kosz<=m;kosz++){ cin >> dzien; cin >> b; kg=0; ti=tn; if(b>=tb[ti]+a[n]*(dzien-td[ti])) // nic nie skosi, bez nowych tarasow cout << 0 << endl; else{ tp[ti+1]=n+1; while((ti>=0) && (b < tb[ti]+a[ tp[ti+1]-1 ]*(dzien-td[ti]))){ long long int t_dzien = td[ti]; long long int t_b = tb[ti]; int t_koniec = tp[ti+1]-1; //cout << "taras ti " << ti << " tp " << tp[ti] << " tk " << t_koniec << " t_b " << t_b << " t_dzien " << t_dzien << " "; a_odc=sufit((b-t_b)/(dzien-t_dzien)); i_odc=ma[a_odc]; if(i_odc < tp[ti]) i_odc=tp[ti]; //cout << "ao " << a_odc << " io " << i_odc << " "; kg+=(sa[ t_koniec ] - sa[ i_odc-1 ])*(dzien-td[ti]); //cout << "kga"<< kg; kg-= (t_koniec-i_odc+1) * (b-t_b); //cout << "kgb"<< kg << " "; if((b<=t_b)||(i_odc==tp[ti]))tn--; ti--; } tn++; td[tn]=dzien; tb[tn]=b; tp[tn]= i_odc; cout << kg << endl; } } 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 | /* * File: main.cpp * Author: luk * * Created on 29 wrzesień 2015, 19:06 */ #include <cstdlib> #include <iostream> using namespace std; #define MILION 1000000 #define POL 500000 long long int sufit(double x){ if(x<0)return 0; long long int y=x; if(x>y)return y+1; else return y; } int a[500005]; long long int sa[500005]; int ile_a[1000005]; int ma[1000005]; long long int td[500005]; // dzien koszenia tarasu long long int tb[500005]; // wysokosc koszenia tarasu int tp[500005]; // poczatek tarasu int main() { // LONG LONG INT - tam gdzie trzeba !!!!!! int n,m; // n - ile pól, m-ile koszen long long int i,j,k,dzien,kosz,b,ti,a_odc,i_odc; long long int kg; cin >> n; cin >> m; for(i=1;i<=n;i++) cin >> a[i]; for(i=0;i<=MILION;i++) ile_a[i]=0; for(i=1;i<=n;i++) ile_a[ a[i] ] ++; k=1; for(i=0;i<=MILION;i++){ ma[i]=k; // pierwsze wystapienie ???? spr gdy nie ma ??? for(j=1;j<=ile_a[i];j++){ // uzupelnienie tablicy a w kolejnosci a[k]=i; k++; } } sa[0]=0; for(i=1;i<=n;i++) sa[i]=sa[i-1]+a[i]; // skumulowane wysokosci td[0]=0; tb[0]=0; tp[0]=1; ti=0; // zerowe zasianie, ti - nr najwyzszego tarasu int tn=0; for(kosz=1;kosz<=m;kosz++){ cin >> dzien; cin >> b; kg=0; ti=tn; if(b>=tb[ti]+a[n]*(dzien-td[ti])) // nic nie skosi, bez nowych tarasow cout << 0 << endl; else{ tp[ti+1]=n+1; while((ti>=0) && (b < tb[ti]+a[ tp[ti+1]-1 ]*(dzien-td[ti]))){ long long int t_dzien = td[ti]; long long int t_b = tb[ti]; int t_koniec = tp[ti+1]-1; //cout << "taras ti " << ti << " tp " << tp[ti] << " tk " << t_koniec << " t_b " << t_b << " t_dzien " << t_dzien << " "; a_odc=sufit((b-t_b)/(dzien-t_dzien)); i_odc=ma[a_odc]; if(i_odc < tp[ti]) i_odc=tp[ti]; //cout << "ao " << a_odc << " io " << i_odc << " "; kg+=(sa[ t_koniec ] - sa[ i_odc-1 ])*(dzien-td[ti]); //cout << "kga"<< kg; kg-= (t_koniec-i_odc+1) * (b-t_b); //cout << "kgb"<< kg << " "; if((b<=t_b)||(i_odc==tp[ti]))tn--; ti--; } tn++; td[tn]=dzien; tb[tn]=b; tp[tn]= i_odc; cout << kg << endl; } } return 0; } |