oj.uz

Submission #915667

# Submission time Handle Problem Language Result Execution time Memory
915667 2024-01-24T13:59:10 Z typ_ik Secret (JOI14_secret) C++17
100 / 100
 391 ms 16464 KB 
#include <bits/stdc++.h> 
#include "secret.h"

#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ll long long 

using namespace std;   

const int N = 1000 + 128;
int t[4 * N][N], a[N];
map <int, map<int, int> > was;
int cnt = 0;

// int Secret(int x, int y) { 
//     return min((ll)1e9, (ll)x+y-(y&1));
// }

int ask(int x, int y) {   
    if (x == -1)
        return y;
    if (y == -1)
        return x;
    if (was.count(x) && was[x].count(y))
        return was[x][y];
    ++cnt;
    return was[x][y] = Secret(x, y);
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v][tl] = a[tl]; 
        return;
    } 
    int tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build(v << 1 | 1, tm + 1, tr);
    
    t[v][tm] = a[tm];
    t[v][tm + 1] = a[tm + 1];
    for (int c = tm - 1; c >= tl; c--)
        t[v][c] = ask(a[c], t[v][c + 1]);
    for (int c = tm + 2; c <= tr; c++)
        t[v][c] = ask(t[v][c - 1], a[c]); 
}

int get(int l, int r, int v, int tl, int tr) {
    if (tl > r || tr < l)
        return -1;
    int tm = (tl + tr) >> 1;

    if (r <= tm)
        return get(l, r, v << 1, tl, tm);
    if (l > tm) 
        return get(l, r, v << 1 | 1, tm + 1, tr);
    
    assert(l <= tm && tm+1 <= r); 

    return ask(t[v][l], t[v][r]);
} 

int n;

void Init(int N, int A[])  {
    n = N;
    for (int x = 0; x < n; x++)
        a[x] = A[x];
    build(1, 0, n - 1);
}

int Query(int L, int R) {
    if (L == R) 
        return a[L];
    if (L + 1 == R)
        return ask(a[L], a[R]);
    return get(L, R, 1, 0, n - 1);
}  

// main() {
//     boost;  
//     srand(time(NULL));
//     solve();
//     return 0;
// }

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 11600 KB Output is correct - number of calls to Secret by Init = 3324, maximum number of calls to Secret by Query = 1
2 Correct 111 ms 11684 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 112 ms 11604 KB Output is correct - number of calls to Secret by Init = 3341, maximum number of calls to Secret by Query = 1
4 Correct 384 ms 16464 KB Output is correct - number of calls to Secret by Init = 7483, maximum number of calls to Secret by Query = 1
5 Correct 387 ms 16300 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
6 Correct 380 ms 16164 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
7 Correct 391 ms 16292 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
8 Correct 387 ms 16292 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
9 Correct 384 ms 16292 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
10 Correct 384 ms 16212 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1