oj.uz

Submission #366269

# Submission time Handle Problem Language Result Execution time Memory
366269 2021-02-13T17:55:30 Z rocks03 Secret (JOI14_secret) C++14
100 / 100
 575 ms 6780 KB 
//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
// #include "secret.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define Re(i, a, b) for(int i = (a); i >= (b); i--)
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

map<pii, int> memo;
int Secret(int x, int y);
int queries = 0;
const int MAXQ = 8000;
int ask(int x, int y){
    if(memo.count({x, y}))
        return memo[{x, y}];
    queries++;
    //if(queries > MAXQ) return 0;
    memo[{x, y}] = Secret(x, y);
  	memo[{y, x}] = memo[{x, y}];
	return memo[{x, y}];
}

const int MAXK = 10;
const int MAXN = 1e3;
int *a, st[MAXK][MAXN], mask[MAXN];

void solve(int l, int r, int lev){
    if(l == r) return;
    int m = (l + r) / 2;
    solve(l, m, lev + 1); solve(m + 1, r, lev + 1);
    st[lev][m] = a[m];
    Re(i, m - 1, l){
        st[lev][i] = ask(a[i], st[lev][i + 1]);
    }
    st[lev][m + 1] = a[m + 1];
    rep(i, m + 2, r + 1){
        st[lev][i] = ask(st[lev][i - 1], a[i]);
    }
    rep(i, m + 1, r + 1){
        mask[i] ^= (1 << lev);
    }
}

void Init(int N, int A[]){
    a = A;
    solve(0, N - 1, 0);
}

int Query(int L, int R){
    if(L == R) return a[L];
    int bits = __builtin_ctz(mask[L] ^ mask[R]);
    return ask(st[bits][L], st[bits][R]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 4076 KB Output is correct - number of calls to Secret by Init = 3324, maximum number of calls to Secret by Query = 1
2 Correct 155 ms 4076 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 157 ms 4076 KB Output is correct - number of calls to Secret by Init = 3341, maximum number of calls to Secret by Query = 1
4 Correct 543 ms 6636 KB Output is correct - number of calls to Secret by Init = 7483, maximum number of calls to Secret by Query = 1
5 Correct 525 ms 6636 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
6 Correct 575 ms 6252 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
7 Correct 546 ms 6780 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
8 Correct 522 ms 6508 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
9 Correct 560 ms 6700 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
10 Correct 518 ms 6636 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1