Submission #1070259

#TimeUsernameProblemLanguageResultExecution timeMemory
1070259AdamGSBrperm (RMI20_brperm)C++17
100 / 100
2316 ms163628 KiB
#include "brperm.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const ll MOD=694202137, PI=2137; const int LIM=5e5+7, LG=20; int hsh[LIM][LG], hshp[LIM][LG], tmp[LIM][LG], tmp2[LIM][LG], pot[2*LG], n; void init(int _n, const char s[]) { n=_n; pot[0]=PI; rep(i, 2*LG-1) pot[i+1]=((ll)pot[i]*(ll)pot[i])%MOD; rep(i, n) hsh[i][0]=hshp[i][0]=s[i]; for(int i=1; i<LG; ++i) { rep(j, n) if(j+(1<<i)<=n) { hsh[j][i]=((ll)hsh[j][i-1]+(ll)hsh[j+(1<<(i-1))][i-1]*(ll)pot[i-1])%MOD; } } rep(i, n) rep(j, LG) tmp[i][j]=s[i]; for(int i=1; i<LG; ++i) { for(int j=0; j<LG-1; ++j) { rep(l, n) if(l+(1<<i)<=n) { tmp2[l][j]=((ll)tmp[l][j+1]+(ll)tmp[l+(1<<(i-1))][j+1]*(ll)pot[j])%MOD; } } rep(l, n) hshp[l][i]=tmp2[l][0]; rep(l, LG) rep(j, n) { tmp[j][l]=tmp2[j][l]; tmp2[j][l]=0; } } } int query(int i, int k) { if(i+(1<<k)>n) return 0; return hsh[i][k]==hshp[i][k]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...