oj.uz

Submission #628241

# Submission time Handle Problem Language Result Execution time Memory
628241 2022-08-13T08:49:47 Z I_am_balancing Secret (JOI14_secret) C++17
100 / 100
 465 ms 4420 KB 
#include "secret.h"

using ll = long long;
int val[12][1005], a[1005], n;

void precalc(ll l, ll r, ll la){
    ll m = (l+r)>>1;
    if(l > r)return;
    val[la][m] = a[m];
    if(l == r)return;
    if(l<=m-1)val[la][m-1] = a[m-1];
    for(ll i = m+1;i<=r;i++)val[la][i]=Secret(val[la][i-1],a[i]);
    for(ll i = m-2;i>=l;i--)val[la][i]=Secret(a[i],val[la][i+1]);
    precalc(l,m-1,la+1);
    precalc(m+1,r,la+1);
}

void Init(int N, int A[]){
    for(ll i = 0;i<N;i++)a[i] = A[i];
    precalc(0,N-1,0);
    n = N;
}
int query(int L, int R, ll l, ll r, ll la){
    ll m = (l+r)>>1;
    if(L <= m && m <= R){
        if(L!=m)
        return Secret(val[la][L],val[la][R]);
        return val[la][R];
    }
    if(m > L)return query(L,R,l,m-1,la+1);
    return query(L,R,m+1,r,la+1);
}

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 2440 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 125 ms 2412 KB Output is correct - number of calls to Secret by Init = 3340, maximum number of calls to Secret by Query = 1
3 Correct 120 ms 2448 KB Output is correct - number of calls to Secret by Init = 3349, maximum number of calls to Secret by Query = 1
4 Correct 444 ms 4348 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
5 Correct 432 ms 4300 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
6 Correct 465 ms 4420 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
7 Correct 438 ms 4316 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
8 Correct 459 ms 4308 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
9 Correct 454 ms 4324 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
10 Correct 438 ms 4316 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1