oj.uz

Submission #366273

# Submission time Handle Problem Language Result Execution time Memory
366273 2021-02-13T18:11:08 Z rocks03 Secret (JOI14_secret) C++14
100 / 100
 568 ms 4516 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());

int Secret(int, int);

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

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

int query(int l, int r, int lev, int ql, int qr){
    int m = (l + r) / 2;
    if(ql <= m && m <= qr){
        if(ql == m + 1) return st[lev][qr];
        else if(qr == m) return st[lev][ql];
        else return Secret(st[lev][ql], st[lev][qr]);
    }
    if(qr <= m) return query(l, m, lev + 1, ql, qr);
    else return query(m + 1, r, lev + 1, ql, qr);
}

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

int Query(int L, int R){
    if(L == R) return a[L];
    else return query(0, N - 1, 0, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 2480 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 142 ms 2416 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 145 ms 2412 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 568 ms 4408 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 509 ms 4460 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 502 ms 4332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 510 ms 4332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 518 ms 4516 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 518 ms 4404 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 511 ms 4332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1