Download 2016/finals/rainbow_string.cpp from hackercupai/hackercup: direct link, hf CLI and curl.
- Browser
- Download file 3.85 kB
-
https://huggingface.co/datasets/hackercupai/hackercup/resolve/main/2016/finals/rainbow_string.cpp
- Command line
-
hf download hf://datasets/hackercupai/hackercup/2016/finals/rainbow_string.cpp
-
curl -L -o rainbow_string.cpp https://huggingface.co/datasets/hackercupai/hackercup/resolve/main/2016/finals/rainbow_string.cpp
3.85 kB
| // RAINBOW STRING | |
| // Official Solution by Jacob Plachta | |
| using namespace std; | |
| template<typename T> T Abs(T x) { return(x<0 ? -x : x); } | |
| template<typename T> T Sqr(T x) { return(x*x); } | |
| string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); } | |
| const int INF = (int)1e9; | |
| const LD EPS = 1e-9; | |
| const LD PI = acos(-1.0); | |
| //#if DEBUG | |
| /*#else | |
| #define GETCHAR getchar_unlocked | |
| #endif*/ | |
| bool Read(int &x) | |
| { | |
| char c,r=0,n=0; | |
| x=0; | |
| for(;;) | |
| { | |
| c=GETCHAR(); | |
| if ((c<0) && (!r)) | |
| return(0); | |
| if ((c=='-') && (!r)) | |
| n=1; | |
| else | |
| if ((c>='0') && (c<='9')) | |
| x=x*10+c-'0',r=1; | |
| else | |
| if (r) | |
| break; | |
| } | |
| if (n) | |
| x=-x; | |
| return(1); | |
| } | |
| int N,SZ; | |
| char S[LIM],C[LIM]; | |
| int sum[LIM][26]; | |
| int sz,P[20][LIM]; | |
| pair<PR,int> V[LIM]; | |
| int O[LIM],ind[LIM]; | |
| vector<int> Q[LIM],A[LIM],B[LIM]; | |
| int BLT[(1<<18)+1]; | |
| void BuildSuffixArray() | |
| { | |
| int i,s; | |
| if (N==1) | |
| { | |
| sz=1; | |
| P[0][0]=0; | |
| return; | |
| } | |
| Fox(i,N) | |
| P[0][i]=S[i]; | |
| for (sz=s=1; s<N; sz++,s<<=1) | |
| { | |
| Fox(i,N) | |
| V[i]=mp(mp(P[sz-1][i],(i+s<N ? P[sz-1][i+s] : -1)),i); | |
| sort(V,V+N); | |
| Fox(i,N) | |
| if ((i) && (V[i].x==V[i-1].x)) | |
| P[sz][V[i].y]=P[sz][V[i-1].y]; | |
| else | |
| P[sz][V[i].y]=i; | |
| } | |
| } | |
| void Update(int i, int v) | |
| { | |
| while (i<=SZ) | |
| { | |
| BLT[i]+=v; | |
| i+=(i&-i); | |
| } | |
| } | |
| int Query(int k) | |
| { | |
| int i=0,b=SZ,t; | |
| while ((b) && (i<SZ)) | |
| { | |
| t=i+b; | |
| if (k>=BLT[t]) | |
| { | |
| i=t; | |
| k-=BLT[t]; | |
| } | |
| b>>=1; | |
| } | |
| return(i); | |
| } | |
| int main() | |
| { | |
| if (DEBUG) | |
| freopen("in.txt","r",stdin); | |
| int T,t; | |
| int M; | |
| int i,j,k,c,s; | |
| LL ans[26]; | |
| Read(T); | |
| Fox1(t,T) | |
| { | |
| Read(N),Read(M); | |
| scanf("%s%s",&S,&C); | |
| Fox(i,M) | |
| { | |
| Read(j),Read(k); | |
| Q[j].pb(k); | |
| } | |
| Fill(sum,0); | |
| Fox1(i,N) | |
| Fox(j,26) | |
| sum[i][j]=sum[i-1][j]+bool(S[i-1]=='A'+j); | |
| BuildSuffixArray(); | |
| Fox(i,N) | |
| { | |
| O[i]=P[sz-1][i]; | |
| ind[O[i]]=i; | |
| } | |
| j=k=1; | |
| FoxR(i,N) | |
| { | |
| j++,k++; | |
| if (C[i]=='G') | |
| j=1; | |
| if (C[i]=='R') | |
| k=1; | |
| if (j<k) | |
| { | |
| A[j].pb(O[i]); | |
| B[k].pb(O[i]); | |
| } | |
| } | |
| Fill(BLT,0),s=0; | |
| for (SZ=1; SZ<N; SZ<<=1); | |
| Fill(ans,0); | |
| Fox1(i,N) | |
| { | |
| Fox(j,Sz(A[i])) | |
| Update(A[i][j]+1,1),s++; | |
| Fox(j,Sz(B[i])) | |
| Update(B[i][j]+1,-1),s--; | |
| Fox(j,Sz(Q[i])) | |
| { | |
| k=ind[Query(Q[i][j]-1)]; | |
| Fox(c,26) | |
| ans[c]+=sum[k+i][c]-sum[k][c]; | |
| } | |
| } | |
| printf("Case #%d:",t); | |
| Fox(i,26) | |
| printf(" %lld",ans[i]); | |
| printf("\n"); | |
| Fox1(i,N+1) | |
| { | |
| A[i].clear(); | |
| B[i].clear(); | |
| Q[i].clear(); | |
| } | |
| } | |
| return(0); | |
| } |