Submission #1068764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068764		ASN49K	Brperm (RMI20_brperm)	C++14	100 / 100	266 ms	225876 KiB

brperm

#include <bits/stdc++.h>
#define pb      push_back
#define all(x)  x.begin(),x.end()
using namespace std;
using u64=uint64_t;

const int N = 500'000;
const int LG=18;
const u64 BASE = 31;
int n,lg;
static u64 cash[LG+1][N+1],inv_cash[LG+1][N+1],pw[LG+1][N+1];
void init(int _n, const char s[])
{
    n=_n;
    while((1<<lg)<=n)
    {
        lg++;
    }
    lg--;
    for(int i=0;i<=lg;i++)
    {
        if(i>0)
        {
            pw[i][1]=pw[i-1][1]*pw[i-1][1];
        }
        else
        {
            pw[i][1]=BASE;
        }
        for(int j=2;j<=n;j++)
        {
            pw[i][j]=pw[i][j-1]*pw[i][1];
        }
    }

    for(int i=0;i<=lg;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cash[i][j]=cash[i][j-1]+pw[i][j]*(s[j-1]-'a');
        }
    }

    for(int i=0;i<n;i++)
    {
        inv_cash[0][i+1]=s[i]-'a';
    }
    for(int i=1;i<=lg;i++)
    {
        for(int j=1;j+(1<<i)-1<=n;j++)
        {
            inv_cash[i][j]=inv_cash[i-1][j]+pw[lg-i][1]*inv_cash[i-1][j+(1<<(i-1))];
        }
    }
}
int query(int l, int k)
{
    l++;
    int r = l+(1<<k)-1;
    //out of bound
    if(r>n)
    {
        return 0;
    }
    return cash[lg-k][r]-cash[lg-k][l-1]==inv_cash[k][l]*pw[lg-k][l];
}

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