oj.uz

Submission #540787

# Submission time Handle Problem Language Result Execution time Memory
540787 2022-03-21T17:47:55 Z Runtime_error_ Secret (JOI14_secret) C++14
100 / 100
 454 ms 4636 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

int a[1111];
int n;
vector<int> pre[4444];
vector<int> suf[4444];
void build(int p,int s,int e)
{
    if(s==e){
        suf[p].push_back(a[s]);
        return;
    }
    int mid=(s+e)/2;
    build(p*2,s,mid);
    build(p*2+1,mid+1,e);
    pre[p].push_back(a[mid+1]);
    for(int i=mid+2;i<=e;i++){
        pre[p].push_back(Secret(pre[p].back(),a[i]));
    }
    suf[p].push_back(a[mid]);
    for(int i=mid-1;i>=s;i--){
        suf[p].push_back(Secret(a[i],suf[p].back()));
    }
}
int get(int p,int s,int e,int a,int b)
{
    int mid=(s+e)/2;
    if(a<=mid&&mid<=b){
        if(b==mid){
            int h=mid-a;
            return suf[p][h];
        }
        else{
            int h=mid-a;
            int h2=b-(mid+1);
            return Secret(suf[p][h],pre[p][h2]);
        }
    }
    if(b<=mid){
        return get(p*2,s,mid,a,b);
    }
    else{
        return get(p*2+1,mid+1,e,a,b);
    }
}
void Init(int N, int A[]){
    n=N;
    for(int i=0;i<n;i++){
        a[i]=A[i];
    }
    build(1,0,n-1);
}

int Query(int L, int R) {
    return get(1,0,n-1,L,R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 2556 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 125 ms 2624 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 128 ms 2628 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 453 ms 4556 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 436 ms 4524 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 4636 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 448 ms 4560 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 439 ms 4556 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 444 ms 4592 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 454 ms 4616 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1