oj.uz

Submission #249958

# Submission time Handle Problem Language Result Execution time Memory
249958 2020-07-16T15:44:55 Z eohomegrownapps Secret (JOI14_secret) C++14
100 / 100
 522 ms 4560 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

int lptr[10][1000];
int rptr[10][1000];
int table[10][1000];

int n;

int findValue(int l, int r, int p){
    if (l==r){
        return table[0][l];
    }
    for (int i = p; i>=0; i--){
        if (lptr[i][l]==-1||rptr[i][r]==-1){continue;}
        if (lptr[i][l]+rptr[i][r]==(r-l+1)){
            return Secret(table[i][l],table[i][r]);
        }
    }
    return -1;
    //assert(1==0);
}
int maxp = 0;

void Init(int N, int A[]) {
    n=N;
    for (int i = 0; i<n; i++){
        table[0][i]=A[i];
        if (i%2==0){
            lptr[0][i]=1;
            rptr[0][i]=-1;
        } else {
            lptr[0][i]=-1;
            rptr[0][i]=1;
        }
    }
    for (int p = 1; (1<<p)<=n; p++){
        int len = 1<<p;
        int cnt = 1<<p;
        bool leftp = true;
        maxp=max(maxp,p);
        for (int i = 0; i<n; i++){
            if (leftp&&cnt==0){
                cnt=1;
                leftp=false;
            } else if ((!leftp)&&cnt==len+1){
                cnt=len;
                leftp=true;
            }
            if (leftp){
                lptr[p][i]=cnt;
                rptr[p][i]=-1;
                table[p][i]=findValue(i,i+cnt-1,p-1);
                cnt--;
            } else {
                lptr[p][i]=-1;
                rptr[p][i]=cnt;
                table[p][i]=findValue(i-cnt+1,i,p-1);
                cnt++;
            }
        }
    }
}

int Query(int L, int R) {
    return findValue(L,R,maxp);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 2552 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 2584 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
3 Correct 143 ms 2552 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 503 ms 4404 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
5 Correct 522 ms 4472 KB Output is correct - number of calls to Secret by Init = 7993, maximum number of calls to Secret by Query = 1
6 Correct 506 ms 4472 KB Output is correct - number of calls to Secret by Init = 7993, maximum number of calls to Secret by Query = 1
7 Correct 505 ms 4472 KB Output is correct - number of calls to Secret by Init = 7993, maximum number of calls to Secret by Query = 1
8 Correct 507 ms 4472 KB Output is correct - number of calls to Secret by Init = 7993, maximum number of calls to Secret by Query = 1
9 Correct 519 ms 4560 KB Output is correct - number of calls to Secret by Init = 7993, maximum number of calls to Secret by Query = 1
10 Correct 505 ms 4472 KB Output is correct - number of calls to Secret by Init = 7993, maximum number of calls to Secret by Query = 1