제출 #915667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915667		typ_ik	비밀 (JOI14_secret)	C++17	100 / 100	391 ms	16464 KiB

secret

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