oj.uz

Submission #915654

# Submission time Handle Problem Language Result Execution time Memory
915654 2024-01-24T13:20:53 Z typ_ik Secret (JOI14_secret) C++17
0 / 100
 367 ms 4640 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((int)1e9, x + 2 * (y/2));
// }

int ask(int x, int y) { 
    if (x > y)
        swap(x, y); 
    if (x == -1)
        return y;
    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);
} 

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

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 2652 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 571570413.
2 Incorrect 97 ms 2800 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 922914816.
3 Incorrect 98 ms 2808 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 429027664.
4 Incorrect 361 ms 4560 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 843251958.
5 Incorrect 362 ms 4572 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 14682184.
6 Incorrect 362 ms 4432 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 850129153.
7 Incorrect 366 ms 4496 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 800201810.
8 Incorrect 367 ms 4432 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 213936592.
9 Incorrect 365 ms 4640 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 286271812.
10 Incorrect 364 ms 4608 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 6251457.