oj.uz

Submission #504168

# Submission time Handle Problem Language Result Execution time Memory
504168 2022-01-10T00:56:58 Z Deepesson Secret (JOI14_secret) C++17
100 / 100
 440 ms 16248 KB 
#include <bits/stdc++.h>
#define MAX 1005
#include "secret.h"
int array[MAX];
int n;
int left[MAX*4][MAX],right[MAX*4][MAX];
int resp=0;
void acessa(int l,int r,int la=0,int ra=n-1,int pos=1){
    if(r<la||ra<l)return;
    int m = (la+ra)/2;
    if(l<=m&&r>=m){
        int posl=l-la;
        int posr=r-(m+1);
        int esq=left[pos][posl];
        if(posr>=0)esq=Secret(esq,right[pos][posr]);
        resp=esq;
        return;
    }
    acessa(l,r,la,m,pos*2);
    acessa(l,r,m+1,ra,(pos*2)+1);
}
void prep(int la=0,int ra=n-1,int pos=1){
    int m = (la+ra)/2;
    {
        int ado=array[m];
        for(int i=m;i!=la-1;--i){
            int cord = i-la;
            if(i!=m){
                ado=Secret(array[i],ado);
            }
            left[pos][cord]=ado;
        }
    }
    {
        int ado=array[m+1];
        for(int i=m+1;i!=ra+1;++i){
            int cord = i-(m+1);
            if(i!=m+1){
                ado=Secret(ado,array[i]);
            }
            right[pos][cord]=ado;
        }
    }
    if(la==ra)return;
    prep(la,m,pos*2);
    prep(m+1,ra,(pos*2)+1);
}
void Init(int N, int A[]){
    n=N;
    for(int i=0;i!=N;++i)array[i]=A[i];
    prep();
}
int Query(int L, int R){
    acessa(L,R);
    return resp;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 8440 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 127 ms 8480 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 124 ms 8388 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 438 ms 16060 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 434 ms 16248 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 432 ms 16116 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 431 ms 16192 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 440 ms 16148 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 438 ms 16136 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 436 ms 16152 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1