oj.uz

Submission #1075974

# Submission time Handle Problem Language Result Execution time Memory
1075974 2024-08-26T10:09:01 Z MyCode Secret (JOI14_secret) C++17
30 / 100
 353 ms 5460 KB 
#include "secret.h"

#include <iostream>
#include <map>

using namespace std;

const int N = 1010;
const int INF = (int)1e9 + 10;

int res[4 * N], a[N], cur_n;

map<pair<int, int>, int> f;

int newSecret(int x, int y){
    if(x == INF) return y;
    if(y == INF) return x;
    if(f.find({x, y}) == f.end())
        f[{x, y}] = Secret(x, y);
    return f[{x, y}];
}

void build(int v, int l, int r){
    if(l == r){
        res[v] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(v * 2, l, mid);
    build(v * 2 + 1, mid + 1, r);
    res[v] = newSecret(res[v * 2], res[v * 2 + 1]);
}

int get(int v, int l, int r, int tl, int tr){
    if(l > tr || r < tl)
        return INF;
    if(l >= tl && r <= tr)
        return res[v];
    int mid = (l + r) / 2;
    return newSecret(get(v * 2, l, mid, tl, tr), get(v * 2 + 1, mid + 1, r, tl, tr));
}

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

int Query(int L, int R) {
    return get(1, 0, cur_n - 1, L, R);
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 101 ms 3560 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 100 ms 3592 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 103 ms 3408 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 329 ms 5460 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 332 ms 5376 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 330 ms 4864 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 353 ms 5204 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 327 ms 5200 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 340 ms 5204 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 332 ms 5112 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 13