oj.uz

Submission #901488

# Submission time Handle Problem Language Result Execution time Memory
901488 2024-01-09T13:04:53 Z anarch_y Secret (JOI14_secret) C++17
100 / 100
 374 ms 4556 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define pb push_back
#define sz(x) (int)x.size()

const int id = 1e9+7;

const int MX = (1<<10);
int tab[10][MX];
vector<int> v;

int F(int x, int y){
    if(x == id) return y;
    if(y == id) return x;
    return Secret(x, y);
}

void divi(int L, int R, int lev){
    if(L == R) return;
    int M = (L+R)/2;
    int nex = lev-1;
    tab[nex][M] = v[M];
    for(int i=M-1; i>=L; i--) tab[nex][i] = F(v[i], tab[nex][i+1]);
    tab[nex][M+1] = v[M+1];
    for(int i=M+2; i<=R; i++) tab[nex][i] = F(tab[nex][i-1], v[i]);
    divi(L, M, nex);
    divi(M+1, R, nex);
}

void Init(int N, int A[]){
    v.resize(MX, id);
    for(int i=0; i<N; i++) v[i] = A[i];
    divi(0, MX-1, 10);
}

int Query(int l, int r){
    if(l == r) return v[l];
    int c = l + MX, d = r + MX;
    int lev = 31 - __builtin_clz(c^d);
    return F(tab[lev][l], tab[lev][r]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 2652 KB Output is correct - number of calls to Secret by Init = 4088, maximum number of calls to Secret by Query = 1
2 Correct 103 ms 2824 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
3 Correct 101 ms 2644 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 374 ms 4356 KB Output is correct - number of calls to Secret by Init = 7991, maximum number of calls to Secret by Query = 1
5 Correct 361 ms 4352 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
6 Correct 360 ms 4556 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
7 Correct 360 ms 4340 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
8 Correct 360 ms 4344 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
9 Correct 356 ms 4348 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
10 Correct 358 ms 4432 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1