oj.uz

Submission #1068764

# Submission time Handle Problem Language Result Execution time Memory
1068764 2024-08-21T11:54:24 Z ASN49K Brperm (RMI20_brperm) C++14
100 / 100
 266 ms 225876 KB 
#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.0 / 13.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 48 ms 40788 KB Output is correct
4 Correct 45 ms 42324 KB Output is correct
5 Correct 43 ms 42316 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 223780 KB Output is correct
2 Correct 266 ms 223940 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 48 ms 40788 KB Output is correct
4 Correct 45 ms 42324 KB Output is correct
5 Correct 43 ms 42316 KB Output is correct
6 Correct 241 ms 223780 KB Output is correct
7 Correct 266 ms 223940 KB Output is correct
8 Correct 242 ms 225872 KB Output is correct
9 Correct 239 ms 225872 KB Output is correct
10 Correct 223 ms 225876 KB Output is correct