#include<bits/stdc++.h> using namespace std; int N,M; vector<int>hajs,gra; vector<int>bylo,poz; string Sgra; void wczytaj(){ cin>>N; hajs.resize(N); for(int i=0;i<N;i++){ cin>>hajs[i]; } cin>>M>>Sgra; bylo.resize(M); gra.resize(M); poz.resize(2*M+666); for(int i=0;i<M;i++) if(Sgra[i]=='P') gra[i]=1; else gra[i]=-1; } int booster,cykl; vector<int>tree; int maxx(int l,int r){ l+=booster; r+=booster; int odp=max(tree[l],tree[r]); while(l/2 != r/2){ if(l%2==0) odp=max(odp,tree[l+1]); if(r%2==1) odp=max(odp,tree[r-1]); l/=2; r/=2; } return odp; } int znajdz(int p,int x){ p+=booster; int y; if(tree[p]>=x)return p-booster; while(p>1){ if(tree[p+1]>=x){ y=p+1; break; } p/=2; } while(y<booster){ if(tree[2*y]>=x) y=y*2; else y=2*y+1; } return y-booster; } long long ANS=-1; void solve(int kto,int gd){//ktory kolega, gdzie w drzewie long long int odj=tree[gd+booster-1];//to co odejmujemy zeby sumy pref byly spoko long long int najw=maxx(gd,gd+cykl)-odj;//ile najwiecej strace long long int kasa=hajs[kto];//ile moge wydac long long int dcykl=tree[gd+cykl+booster]-odj;//ile co cykl trace/zyskuje long long int kon;//gdzie przegrywa if(najw<kasa && dcykl<=0){//on nigdy nie przegra!!! return; } //printf("kto=%d gd=%d odj=%d najw=%d kasa=%d dcykl=%d cykl=%d\n", // kto,gd,odj,najw,kasa,dcykl,cykl); if(najw>=kasa){ kon=znajdz(gd,kasa+odj);//tu moze byc blad!!!!!!!!!!!! ale raczej spoko //printf("easy kon=%d\n",kon); if((ANS==-1 || (1LL*(kon-gd)*N+kto+1)<ANS) && (1LL*(kon-gd)*N+kto+1)>0){ ANS=1LL*(kon-gd)*N+kto+1; // printf("%lld safsfas\n",ANS); } } long long int ileOb=(kasa-najw)/dcykl;//ile obiegow cykli long long int ileTr=(dcykl*ileOb);//ile trace po cyklach kon=znajdz(gd,kasa+odj-ileTr);//tu moze byc blad!!!!!!!!!!!! ale raczej spoko //printf("kon=%d\n",kon); //if(kon-gd<0)cout<<"dupa"; if((ANS==-1 || (1LL*(cykl+1)*N*ileOb+kto+1LL+1LL*(kon-gd)*N)<ANS) && (1LL*(cykl+1)*N*ileOb+kto+1LL+1LL*(kon-gd)*N)>0) ANS=1LL*(cykl+1)*N*ileOb+kto+1LL+1LL*(kon-gd)*N; } vector<pair<int,int> >stos;//kto gdzie void dodaj(int x,int pz){ while(x<N){ stos.push_back(make_pair(x,pz)); x+=M; } } void sciagaj(){ while(!stos.empty()){ solve(stos.back().first,stos.back().second); stos.pop_back(); } } void makeTree(int kon){ cykl=((kon-1)/2)-1;//dl cyklu booster=2; while(kon>booster) booster*=2; tree.resize(0); tree.resize(2*booster+2); for(int i=booster+1;i<booster+kon;i++){ tree[i]=gra[poz[i-booster]]; tree[i]+=tree[i-1]; } for(int i=booster-1;i>=1;i--) tree[i]=max(tree[2*i],tree[2*i+1]); //for(int i=booster+1;i<booster+kon;i++) //printf("%d: %d\n",i-booster,tree[i]); } void skacz(){ for(int i=0;i<M;i++){ int p=i,j=1;//p pozycja dla stanu W,P, j pozycja w drzewie while(bylo[p]<2){ //printf("p=%d j=%d\n",p,j); if(bylo[p]==0)dodaj(p,j); poz[j]=p;//jaki stan na j tej pozycji w drzewie bylo[p]++; j++; p=(p+N)%M; } //printf(" %d \n",j); if(j>1)makeTree(j);//j ilosc elementow sciagaj(); } } int main(){ cout.sync_with_stdio(0); wczytaj(); skacz(); cout<<ANS; 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 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 140 141 | #include<bits/stdc++.h> using namespace std; int N,M; vector<int>hajs,gra; vector<int>bylo,poz; string Sgra; void wczytaj(){ cin>>N; hajs.resize(N); for(int i=0;i<N;i++){ cin>>hajs[i]; } cin>>M>>Sgra; bylo.resize(M); gra.resize(M); poz.resize(2*M+666); for(int i=0;i<M;i++) if(Sgra[i]=='P') gra[i]=1; else gra[i]=-1; } int booster,cykl; vector<int>tree; int maxx(int l,int r){ l+=booster; r+=booster; int odp=max(tree[l],tree[r]); while(l/2 != r/2){ if(l%2==0) odp=max(odp,tree[l+1]); if(r%2==1) odp=max(odp,tree[r-1]); l/=2; r/=2; } return odp; } int znajdz(int p,int x){ p+=booster; int y; if(tree[p]>=x)return p-booster; while(p>1){ if(tree[p+1]>=x){ y=p+1; break; } p/=2; } while(y<booster){ if(tree[2*y]>=x) y=y*2; else y=2*y+1; } return y-booster; } long long ANS=-1; void solve(int kto,int gd){//ktory kolega, gdzie w drzewie long long int odj=tree[gd+booster-1];//to co odejmujemy zeby sumy pref byly spoko long long int najw=maxx(gd,gd+cykl)-odj;//ile najwiecej strace long long int kasa=hajs[kto];//ile moge wydac long long int dcykl=tree[gd+cykl+booster]-odj;//ile co cykl trace/zyskuje long long int kon;//gdzie przegrywa if(najw<kasa && dcykl<=0){//on nigdy nie przegra!!! return; } //printf("kto=%d gd=%d odj=%d najw=%d kasa=%d dcykl=%d cykl=%d\n", // kto,gd,odj,najw,kasa,dcykl,cykl); if(najw>=kasa){ kon=znajdz(gd,kasa+odj);//tu moze byc blad!!!!!!!!!!!! ale raczej spoko //printf("easy kon=%d\n",kon); if((ANS==-1 || (1LL*(kon-gd)*N+kto+1)<ANS) && (1LL*(kon-gd)*N+kto+1)>0){ ANS=1LL*(kon-gd)*N+kto+1; // printf("%lld safsfas\n",ANS); } } long long int ileOb=(kasa-najw)/dcykl;//ile obiegow cykli long long int ileTr=(dcykl*ileOb);//ile trace po cyklach kon=znajdz(gd,kasa+odj-ileTr);//tu moze byc blad!!!!!!!!!!!! ale raczej spoko //printf("kon=%d\n",kon); //if(kon-gd<0)cout<<"dupa"; if((ANS==-1 || (1LL*(cykl+1)*N*ileOb+kto+1LL+1LL*(kon-gd)*N)<ANS) && (1LL*(cykl+1)*N*ileOb+kto+1LL+1LL*(kon-gd)*N)>0) ANS=1LL*(cykl+1)*N*ileOb+kto+1LL+1LL*(kon-gd)*N; } vector<pair<int,int> >stos;//kto gdzie void dodaj(int x,int pz){ while(x<N){ stos.push_back(make_pair(x,pz)); x+=M; } } void sciagaj(){ while(!stos.empty()){ solve(stos.back().first,stos.back().second); stos.pop_back(); } } void makeTree(int kon){ cykl=((kon-1)/2)-1;//dl cyklu booster=2; while(kon>booster) booster*=2; tree.resize(0); tree.resize(2*booster+2); for(int i=booster+1;i<booster+kon;i++){ tree[i]=gra[poz[i-booster]]; tree[i]+=tree[i-1]; } for(int i=booster-1;i>=1;i--) tree[i]=max(tree[2*i],tree[2*i+1]); //for(int i=booster+1;i<booster+kon;i++) //printf("%d: %d\n",i-booster,tree[i]); } void skacz(){ for(int i=0;i<M;i++){ int p=i,j=1;//p pozycja dla stanu W,P, j pozycja w drzewie while(bylo[p]<2){ //printf("p=%d j=%d\n",p,j); if(bylo[p]==0)dodaj(p,j); poz[j]=p;//jaki stan na j tej pozycji w drzewie bylo[p]++; j++; p=(p+N)%M; } //printf(" %d \n",j); if(j>1)makeTree(j);//j ilosc elementow sciagaj(); } } int main(){ cout.sync_with_stdio(0); wczytaj(); skacz(); cout<<ANS; return 0; } |