oj.uz

Submission #1068762

# Submission time Handle Problem Language Result Execution time Memory
1068762 2024-08-21T11:54:07 Z ASN49K Brperm (RMI20_brperm) C++14
13 / 100
 200 ms 116628 KB 
#include <bits/stdc++.h>
#define pb      push_back
#define all(x)  x.begin(),x.end()
using namespace std;
using u64=uint32_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.0 / 13.0

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

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Incorrect 38 ms 21412 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 116628 KB Output is correct
2 Incorrect 200 ms 116308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Incorrect 38 ms 21412 KB Output isn't correct
4 Halted 0 ms 0 KB -