#include<bits/stdc++.h> using namespace std; typedef long long int ll; int twe[1000009],twy[1000009]; pair<int,int> td[4200007]; int N; list<int> lista; int nwd(int a, int b) { while(a>0 && b>0) if(a>b) a%=b; else b%=a; return a+b; } void Init(int n) { for(N=1;N<=n;N<<=1); //printf("%d %d\n",n,N); for(int i=0;i<N<<1;++i) td[i]=make_pair(1e9,1e9); } void Insert(int pos, int v) { pos+=N; td[pos].first=v; td[pos].second=v; pos>>=1; while(pos>0) { td[pos].first=min(td[pos<<1].first,td[(pos<<1)+1].first); td[pos].second=max(td[pos<<1].second,td[(pos<<1)+1].second); pos>>=1; } } int Query(int p, int v) { int ak=1,pocz=0,kon=N-1; while(ak<N) { //printf("%d %d %d %d\n",ak,v,td[ak*2].first,td[ak*2].second); if((pocz+kon)>>1>=p && td[ak*2].first<=v && td[ak*2].second>=v) { ak<<=1; kon=(pocz+kon)>>1; } else { ak=ak*2+1; pocz=(pocz+kon)/2+1; } } return ak-N; } int Qmin(int p, int k, int ak=1, int pocz=0, int kon=N-1) { if(pocz>k || kon<p) return 1e9; if(pocz>=p && kon<=k) return td[ak].first; return min(Qmin(p,k,ak<<1,pocz,(pocz+kon)>>1),Qmin(p,k,ak*2+1,1+((pocz+kon)>>1),kon)); } int main() { ll n,m,nw,nww; int sum,me,l; ll wyn=1e18+9,ob,w; char z; scanf("%lld",&n); for(int i=1;i<=n;++i) scanf("%d",&twe[i]); scanf("%lld",&m); nw=nwd(n,m); nww=(ll)n*(ll)m/(ll)nw; //printf("%lld %lld\n",nw,nww); for(int i=1;i<=m;++i) { scanf(" %c",&z); if(z=='W') twy[i]=1; else twy[i]=-1; } for(int i=1;i<=nw;++i) { sum=0; Init(m/nw*2+1); Insert(0,0); for(int j=i;j<=m;j+=nw) sum-=twy[j]; if(sum<=0) continue; l=i; for(int j=1;j<=m/nw*2;++j) { Insert(j,td[N+j-1].first+twy[1+((l-1)%m)]); //UWAGA l=(l+n)%m; if(l==0) l=m; } //for(int z=N;z<=N+m/nw*2;++z) printf("%d ",td[z].first); printf("\n"); l=0; //printf("%d\n",sum); for(int j=i;j<=n;j+=nw) { me=Qmin(l,l+m/nw)-td[N+l].first; ob=(twe[j]+me+sum-1)/sum; twe[j]-=ob*sum; w=n*((ll)Query(l,-1*twe[j]+td[N+l].first)-l-1)+j; wyn=min(wyn,ob*nww+w); //Printf("%d %d %lld %d %d %lld\n",j,me,ob,twe[j],td[N+l].first,w); l=(l+(n%m)/nw)%(m/nw); } } if(wyn==1e18+9) printf("-1"); else printf("%lld",wyn); 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 | #include<bits/stdc++.h> using namespace std; typedef long long int ll; int twe[1000009],twy[1000009]; pair<int,int> td[4200007]; int N; list<int> lista; int nwd(int a, int b) { while(a>0 && b>0) if(a>b) a%=b; else b%=a; return a+b; } void Init(int n) { for(N=1;N<=n;N<<=1); //printf("%d %d\n",n,N); for(int i=0;i<N<<1;++i) td[i]=make_pair(1e9,1e9); } void Insert(int pos, int v) { pos+=N; td[pos].first=v; td[pos].second=v; pos>>=1; while(pos>0) { td[pos].first=min(td[pos<<1].first,td[(pos<<1)+1].first); td[pos].second=max(td[pos<<1].second,td[(pos<<1)+1].second); pos>>=1; } } int Query(int p, int v) { int ak=1,pocz=0,kon=N-1; while(ak<N) { //printf("%d %d %d %d\n",ak,v,td[ak*2].first,td[ak*2].second); if((pocz+kon)>>1>=p && td[ak*2].first<=v && td[ak*2].second>=v) { ak<<=1; kon=(pocz+kon)>>1; } else { ak=ak*2+1; pocz=(pocz+kon)/2+1; } } return ak-N; } int Qmin(int p, int k, int ak=1, int pocz=0, int kon=N-1) { if(pocz>k || kon<p) return 1e9; if(pocz>=p && kon<=k) return td[ak].first; return min(Qmin(p,k,ak<<1,pocz,(pocz+kon)>>1),Qmin(p,k,ak*2+1,1+((pocz+kon)>>1),kon)); } int main() { ll n,m,nw,nww; int sum,me,l; ll wyn=1e18+9,ob,w; char z; scanf("%lld",&n); for(int i=1;i<=n;++i) scanf("%d",&twe[i]); scanf("%lld",&m); nw=nwd(n,m); nww=(ll)n*(ll)m/(ll)nw; //printf("%lld %lld\n",nw,nww); for(int i=1;i<=m;++i) { scanf(" %c",&z); if(z=='W') twy[i]=1; else twy[i]=-1; } for(int i=1;i<=nw;++i) { sum=0; Init(m/nw*2+1); Insert(0,0); for(int j=i;j<=m;j+=nw) sum-=twy[j]; if(sum<=0) continue; l=i; for(int j=1;j<=m/nw*2;++j) { Insert(j,td[N+j-1].first+twy[1+((l-1)%m)]); //UWAGA l=(l+n)%m; if(l==0) l=m; } //for(int z=N;z<=N+m/nw*2;++z) printf("%d ",td[z].first); printf("\n"); l=0; //printf("%d\n",sum); for(int j=i;j<=n;j+=nw) { me=Qmin(l,l+m/nw)-td[N+l].first; ob=(twe[j]+me+sum-1)/sum; twe[j]-=ob*sum; w=n*((ll)Query(l,-1*twe[j]+td[N+l].first)-l-1)+j; wyn=min(wyn,ob*nww+w); //Printf("%d %d %lld %d %d %lld\n",j,me,ob,twe[j],td[N+l].first,w); l=(l+(n%m)/nw)%(m/nw); } } if(wyn==1e18+9) printf("-1"); else printf("%lld",wyn); return 0; } |