Submission #1075974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075974		MyCode	Secret (JOI14_secret)	C++17	30 / 100	353 ms	5460 KiB

secret

#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 / 100