oj.uz

Submission #540770

# Submission time Handle Problem Language Result Execution time Memory
540770 2022-03-21T17:10:21 Z Hazem Secret (JOI14_secret) C++14
100 / 100
 538 ms 8260 KB 
#include "secret.h"
#include <bits/stdc++.h>

const int M = 1e3+10;

int a[M],n;
int ans[4*M][M];

void build(int v,int tl,int tr){

    if(tl==tr)
        return ;

    int mid = (tl+tr)/2;

    ans[v][mid] = a[mid];
    ans[v][mid+1] = a[mid+1];

    for(int i=mid+2;i<=tr;i++)
        ans[v][i] = Secret(ans[v][i-1],a[i]);

    for(int i=mid-1;i>=tl;i--)
        ans[v][i] = Secret(a[i],ans[v][i+1]);

    build(v*2,tl,mid);
    build(v*2+1,mid+1,tr);
}

int get(int v,int tl,int tr,int l,int r){

    int mid = (tl+tr)/2;
    if(mid>=l&&mid<=r)
        if(r==mid)
            return ans[v][l];
        else
            return Secret(ans[v][l],ans[v][r]);

    if(r<=mid)
        return get(v*2,tl,mid,l,r);
    else
        return get(v*2+1,mid+1,tr,l,r);
}


void Init(int N, int A[]) {

    for(int i=0;i<N;i++)
        a[i+1] = A[i];

    n = N;
    build(1,1,N);
}

int Query(int L, int R) {

    if(L==R)
        return a[L+1];

    return get(1,1,n,L+1,R+1);
}

Compilation message

secret.cpp: In function 'int get(int, int, int, int, int)':
secret.cpp:32:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   32 |     if(mid>=l&&mid<=r)
      |       ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 4392 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 138 ms 4304 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 141 ms 4352 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 538 ms 8176 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 494 ms 8188 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 479 ms 8260 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 483 ms 8212 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 492 ms 8216 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 491 ms 8232 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 479 ms 8140 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1