oj.uz

Submission #366268

# Submission time Handle Problem Language Result Execution time Memory
366268 2021-02-13T17:54:21 Z rocks03 Secret (JOI14_secret) C++14
0 / 100
 508 ms 4972 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);
    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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 2924 KB Wrong Answer: Query(108, 484) - expected : 860102144, actual : 0.
2 Incorrect 142 ms 2924 KB Wrong Answer: Query(250, 479) - expected : 46309441, actual : 0.
3 Incorrect 141 ms 2944 KB Wrong Answer: Query(182, 210) - expected : 951199962, actual : 0.
4 Incorrect 497 ms 4972 KB Wrong Answer: Query(31, 829) - expected : 864567342, actual : 0.
5 Incorrect 502 ms 4844 KB Wrong Answer: Query(586, 800) - expected : 10668054, actual : 0.
6 Incorrect 500 ms 4864 KB Wrong Answer: Query(876, 880) - expected : 690423497, actual : 0.
7 Incorrect 502 ms 4864 KB Wrong Answer: Query(40, 988) - expected : 795348017, actual : 0.
8 Incorrect 504 ms 4860 KB Wrong Answer: Query(169, 994) - expected : 96654344, actual : 0.
9 Incorrect 508 ms 4844 KB Wrong Answer: Query(10, 986) - expected : 835468903, actual : 0.
10 Incorrect 501 ms 4972 KB Wrong Answer: Query(116, 971) - expected : 270360962, actual : 0.