oj.uz

Submission #494514

# Submission time Handle Problem Language Result Execution time Memory
494514 2021-12-15T16:39:35 Z leaked Brperm (RMI20_brperm) C++14
100 / 100
 2043 ms 138428 KB 
#include <bits/stdc++.h>
//#include "brperm.h"
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fast_rmi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
const int N=(1<<19);
int pref[N][26];
int work[N][20];

int answ[N][20];
string s;
void init(int n,const char t[]){
    for(int i=0;i<n;i++){
        s+=t[i];
        for(int j=0;j<26;j++){
            pref[i][j]=(i?pref[i-1][j]:0);
        }
        pref[i][s[i]-'a']++;
    }
    for(int j=0;j<20;j++){
        for(int i=0;i<(1<<(j));i++){
            ///TODO
            for(int k=0;k<j;k++){
                if((1<<k)&i)
                    work[i][j]+=(1<<(j-k-1));
            }
//            answ[i][j]=-1;
        }
        for(int i=0;i<n;i++)
            answ[i][j]=-1;
    }
}
int query(int i,int k){
    if(k>=20 || i+(1<<(k))-1>=sz(s))
        return 0;
    if(answ[i][k]!=-1)
        return answ[i][k];
    int l=i,r=i+(1<<(k))-1;
    for(int j=0;j<26;j++){
        if((pref[r][j]-(l?pref[l-1][j]:0))==(r-l+1))
            return 1;
    }
    int ok=1;
    for(int i=l;i<=r;i++){
        int id=l+work[(i-l)][k];
        if(s[i]!=s[id]){
            ok=0;
            break;
        }
    }
    answ[i][k]=ok;
    return ok;
}
//char * a;
//char a[199];
//signed main(){
//    cin>>a;
//    int n=strlen(a);
//    init(n,a);
//    int tt=4;
//    while(tt--){
//        int i,j;
//        cin>>i>>j;
//        cout<<query(i,j)<<endl;
//    }
//}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 41560 KB Output is correct
2 Correct 68 ms 41432 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 41560 KB Output is correct
2 Correct 68 ms 41432 KB Output is correct
3 Correct 128 ms 60744 KB Output is correct
4 Correct 135 ms 60712 KB Output is correct
5 Correct 127 ms 60672 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2043 ms 133612 KB Output is correct
2 Correct 378 ms 138428 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 41560 KB Output is correct
2 Correct 68 ms 41432 KB Output is correct
3 Correct 128 ms 60744 KB Output is correct
4 Correct 135 ms 60712 KB Output is correct
5 Correct 127 ms 60672 KB Output is correct
6 Correct 2043 ms 133612 KB Output is correct
7 Correct 378 ms 138428 KB Output is correct
8 Correct 376 ms 138428 KB Output is correct
9 Correct 377 ms 138352 KB Output is correct
10 Correct 374 ms 138412 KB Output is correct