Submission #1094525

#TimeUsernameProblemLanguageResultExecution timeMemory
1094525alexddBrperm (RMI20_brperm)C++17
0 / 100
3044 ms154200 KiB
#include "brperm.h" #include <bits/stdc++.h> using namespace std; const long long MOD = 1e9+9; long long p[530005]; int put(int a, int exp) { if(exp==0) return 1; if(exp%2==0) return put(a*a%MOD,exp/2); else return put(a*a%MOD,exp/2)*a%MOD; } long long hsh[500005][19]; long long normal[500005][19]; void init(int n, const char s[]) { p[0]=1; p[1]=31; for(int i=2;i<=(1<<19);i++) p[i] = (p[i-1]*p[1])%MOD; for(int i=0;i<n;i++) { hsh[i][0] = normal[i][0] = s[i]; } for(int k=1;k<19;k++) { for(int i=0;i+(1<<k)-1<n;i++) { hsh[i][k] = (hsh[i][k-1] + hsh[i+(1<<(k-1))][k-1]*p[(1<<(18-k))])%MOD; for(int j=0;j<(1<<k);j++) { normal[i][k] = (normal[i][k] + s[i+j]*p[j*(1<<(18-k))])%MOD; } } } } int query(int i, int k) { return hsh[i][k] == normal[i][k]; } /* axxyxxyb 0 3 1 1 0 2 3 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...