oj.uz

Submission #485223

# Submission time Handle Problem Language Result Execution time Memory
485223 2021-11-06T15:22:37 Z ETK Brperm (RMI20_brperm) C++14
100 / 100
 477 ms 126152 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 588 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 84 ms 25304 KB Output is correct
4 Correct 83 ms 25384 KB Output is correct
5 Correct 106 ms 25288 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 121084 KB Output is correct
2 Correct 434 ms 126152 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 84 ms 25304 KB Output is correct
4 Correct 83 ms 25384 KB Output is correct
5 Correct 106 ms 25288 KB Output is correct
6 Correct 448 ms 121084 KB Output is correct
7 Correct 434 ms 126152 KB Output is correct
8 Correct 477 ms 126072 KB Output is correct
9 Correct 474 ms 126044 KB Output is correct
10 Correct 454 ms 126096 KB Output is correct