oj.uz

Submission #915662

# Submission time Handle Problem Language Result Execution time Memory
915662 2024-01-24T13:40:26 Z typ_ik Secret (JOI14_secret) C++17
30 / 100
 429 ms 5712 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], 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] = a[tl]; 
        return;
    } 
    int tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build(v << 1 | 1, tm + 1, tr);
    t[v] = ask(t[v << 1], t[v << 1 | 1]);
}

int get(int l, int r, int v, int tl, int tr) {
    if (tl > r || tr < l)
        return -1;
    if (l <= tl && tr <= r)
        return t[v];
    int tm = (tl + tr) >> 1;
    return ask(get(l, r, v << 1, tl, tm),
            get(l, r, v << 1 | 1, tm + 1, tr));
} 

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) {
    return get(L, R, 1, 0, n - 1);
} 

// void solve() {
//     n = 10; 
//     for (int i = 0; i < n; i++)
//         a[i] = rand() % int(1e9) + 1;  
//     build(1, 0, n - 1);  
//     int q = 1000; 
//     while (q--) {
//         int L, R;
//         L = rand() % n;
//         R = rand() % (n - L - 1) + L;  
//         int res = a[L];
//         for (int c = L + 1; c <= R; c++)
//             res = Secret(res, a[c]);
//         int we = get(L, R, 1, 0, n - 1);
//         if (we != res) {
//             cout << "MISTAKE WAS FOUND!\n";
//             cout << n << '\n';
//             for (int c = 0; c < n; c++)
//                 cout << a[c] << ' ';
//             cout << '\n';
//             cout << L << ' ' << R << '\n';
//             watch(res);
//             watch(we);
//             return;
//         } 
//     }
// }

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

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 121 ms 3408 KB Output is partially correct - number of calls to Secret by Init = 510, maximum number of calls to Secret by Query = 10
2 Partially correct 119 ms 3412 KB Output is partially correct - number of calls to Secret by Init = 511, maximum number of calls to Secret by Query = 12
3 Partially correct 121 ms 3572 KB Output is partially correct - number of calls to Secret by Init = 512, maximum number of calls to Secret by Query = 11
4 Partially correct 392 ms 5640 KB Output is partially correct - number of calls to Secret by Init = 998, maximum number of calls to Secret by Query = 13
5 Partially correct 399 ms 5712 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 13
6 Partially correct 373 ms 4944 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 4
7 Partially correct 393 ms 5456 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 14
8 Partially correct 429 ms 5204 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 15
9 Partially correct 397 ms 5104 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 14
10 Partially correct 410 ms 5204 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 13