oj.uz

Submission #373495

# Submission time Handle Problem Language Result Execution time Memory
373495 2021-03-04T20:27:56 Z BartolM Secret (JOI14_secret) C++17
100 / 100
 508 ms 4660 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int MAXN=1005;
const int LOG=12;

int n;
int p[MAXN];
int val[LOG][MAXN];

void rek(int l, int r, int br) {
    if (l==r) return;
    int mid=(l+r)/2;

    val[br][mid]=p[mid];
    for (int i=mid-1; i>=l; --i) val[br][i]=Secret(p[i], val[br][i+1]);

    val[br][mid+1]=p[mid+1];
    for (int i=mid+2; i<=r; ++i) val[br][i]=Secret(val[br][i-1], p[i]);

    rek(l, mid, br+1);
    rek(mid+1, r, br+1);
}

int solve(int a, int b, int br=0, int lo=0, int hi=n-1) {
    int mid=(lo+hi)/2;
    if (a>mid) return solve(a, b, br+1, mid+1, hi);
    if (b<=mid) return solve(a, b, br+1, lo, mid);
    return Secret(val[br][a], val[br][b]);
}

void Init(int N, int A[]) {
    n=N;
    for (int i=0; i<n; ++i) p[i]=A[i];
    rek(0, n-1, 0);
}

int Query(int L, int R) {
    if (L==R) return p[L];
    return solve(L, R);
}

/*
8
1 4 7 2 5 8 3 6
1
0 3
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 2540 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 2668 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 141 ms 2540 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 502 ms 4588 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 499 ms 4408 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 508 ms 4660 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 503 ms 4460 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 503 ms 4588 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 505 ms 4588 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 504 ms 4588 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1