Submission #373495

#	Time	Username	Problem	Language	Result	Execution time	Memory
373495		BartolM	Secret (JOI14_secret)	C++17	100 / 100	508 ms	4660 KiB

secret

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