Submission #494514

#TimeUsernameProblemLanguageResultExecution timeMemory
494514leakedBrperm (RMI20_brperm)C++14
100 / 100
2043 ms138428 KiB
#include <bits/stdc++.h> //#include "brperm.h" #define f first #define s second #define m_p make_pair #define vec vector #define sz(x) (int)(x).size() #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define fast_rmi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; const int N=(1<<19); int pref[N][26]; int work[N][20]; int answ[N][20]; string s; void init(int n,const char t[]){ for(int i=0;i<n;i++){ s+=t[i]; for(int j=0;j<26;j++){ pref[i][j]=(i?pref[i-1][j]:0); } pref[i][s[i]-'a']++; } for(int j=0;j<20;j++){ for(int i=0;i<(1<<(j));i++){ ///TODO for(int k=0;k<j;k++){ if((1<<k)&i) work[i][j]+=(1<<(j-k-1)); } // answ[i][j]=-1; } for(int i=0;i<n;i++) answ[i][j]=-1; } } int query(int i,int k){ if(k>=20 || i+(1<<(k))-1>=sz(s)) return 0; if(answ[i][k]!=-1) return answ[i][k]; int l=i,r=i+(1<<(k))-1; for(int j=0;j<26;j++){ if((pref[r][j]-(l?pref[l-1][j]:0))==(r-l+1)) return 1; } int ok=1; for(int i=l;i<=r;i++){ int id=l+work[(i-l)][k]; if(s[i]!=s[id]){ ok=0; break; } } answ[i][k]=ok; return ok; } //char * a; //char a[199]; //signed main(){ // cin>>a; // int n=strlen(a); // init(n,a); // int tt=4; // while(tt--){ // int i,j; // cin>>i>>j; // cout<<query(i,j)<<endl; // } //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...