Submission #485223

#	Time	Username	Problem	Language	Result	Execution time	Memory
485223		ETK	Brperm (RMI20_brperm)	C++14	100 / 100	477 ms	126152 KiB

brperm

#include <bits/stdc++.h>
#include "brperm.h"
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=5e5+5,P=1e9+7,B=37;
int f[N][20],g[N][20],base[20],b[N][20],t[N],n;
int mul(int a,int b){return 1ll*a*b%P;}
int add(int a,int b){return a+b>=P?a+b-P:a+b;}
int sub(int a,int b){return a-b<0?a-b+P:a-b;}
void init(int m,const char s[]){
    n=m;
    base[19]=B;
    per(i,18,0)base[i]=mul(base[i+1],base[i+1]);
    rep(i,0,19){
        b[0][i]=1;
        rep(j,1,n-1)b[j][i]=mul(b[j-1][i],base[i]);
    }
    rep(i,0,19){//straighthash
        t[0]=s[0]-'a'+1;
        rep(j,1,n-1)t[j]=add(s[j]-'a'+1,mul(t[j-1],base[i]));
        f[0][i]=t[(1<<i)-1];
        rep(j,1,n-(1<<i)){
            f[j][i]=sub(t[j+(1<<i)-1],mul(t[j-1],b[1<<i][i]));
        }
    }
    rep(i,0,n-1)g[i][0]=s[i]-'a'+1;
    //brpermhash
    rep(j,1,19)rep(i,0,n-(1<<j)){
        g[i][j]=add(mul(g[i][j-1],base[j]),g[i+(1<<(j-1))][j-1]);
    }
}
int query(int i,int k){return i+(1<<k)<=n&&f[i][k]==g[i][k];}

• Subtask 1: 13 / 13
• Subtask 2: 37 / 37
• Subtask 3: 17 / 17
• Subtask 4: 33 / 33