oj.uz

Submission #568270

# Submission time Handle Problem Language Result Execution time Memory
568270 2022-05-25T04:44:24 Z gg123_pe Secret (JOI14_secret) C++14
100 / 100
 516 ms 12224 KB 
#include <bits/stdc++.h>
#include "secret.h"
 
using namespace std; 
 
typedef long long ll; 
typedef pair<ll,ll> ii; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)
 
#define ff first 
#define ss second 
 
const int N = 1005; 
const ll inf = 1e17 + 100; 
 
 
int n, a[N], L[N][N], R[N][N]; 
 
void go(int l, int r){
    if(l == r){
        L[l][l] = R[l][l] = a[l]; 
        return ;
    }
    int m = (l+r)>>1; 
    
    L[m][m] = a[m]; 
    fa(i,m-1,l) L[m][i] = Secret(a[i], L[m][i+1]); 
 
    R[m+1][m+1] = a[m+1];
    f(i,m+2,r+1) R[m+1][i] = Secret(R[m+1][i-1], a[i]);   
 
    go(l, m), go(m+1, r); 
}
void Init(int ni, int x[]){
    n = ni; 
    f(i,0,n) a[i] = x[i];
 
    go(0, n-1);  
}
 
int Query(int x, int y){
    int l = 0, r = n-1; 
    while(1){
        int m = (l+r)>>1; 
        if(y == m)
            return L[y][x]; 
        if(x == m+1)
            return R[x][y];
        if(x <= m and m+1 <= y)
            return Secret(L[m][x], R[m+1][y]); 
 
        if(y < m) r = m;  
        else l = m+1; 
    }
    return -1; 
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 6288 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 141 ms 6348 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 127 ms 6352 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 469 ms 12128 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 472 ms 12104 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 516 ms 12188 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 513 ms 12152 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 457 ms 12044 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 475 ms 12224 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 513 ms 12036 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1