Submission #411496

#	Time	Username	Problem	Language	Result	Execution time	Memory
411496		AlperenT	Secret (JOI14_secret)	C++17	100 / 100	582 ms	4620 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

const int N = 1e3 + 5;

int arr[N], n;

struct Item{
    int m;
    vector<int> left, right;
};

Item tree[N * 4];

void build(int v, int l, int r){
    if(l == r) tree[v] = {l, {arr[l]}, {}};
    else{
        int m = l + (r - l) / 2;
        build(v * 2, l, m);
        build(v * 2 + 1, m + 1, r);

        int curval = arr[m];
        tree[v] = {m, {arr[m]}, {}};

        for(int i = m - 1; i >= l; i--){
            curval = Secret(arr[i], curval);
            tree[v].left.push_back(curval);
        }

        curval = arr[m + 1];

        if(m + 1 <= r) tree[v].right.push_back(curval);

        for(int i = m + 2; i <= r; i++){
            curval = Secret(curval, arr[i]);
            tree[v].right.push_back(curval);
        }
    }
}

int doquery(int v, int tl, int tr, int l, int r){
    if(l >= tl && r <= tr && tree[v].m >= l && tree[v].m <= r){
        if(r - tree[v].m - 1 >= 0){
            return Secret(tree[v].left[tree[v].m - l], tree[v].right[r - tree[v].m - 1]);
        }
        else return tree[v].left[tree[v].m - l];
    }
    else{
        int tm = tl + (tr - tl) / 2;
        if(r <= tm) return doquery(v * 2, tl, tm, l, r);
        else return doquery(v * 2 + 1, tm + 1, tr, l, r);
    }
}

void Init(int nn, int a[]) {
    n = nn;

    for(int i = 0; i < n; i++) arr[i] = a[i];

    build(1, 0, n - 1);
}

int Query(int l, int r) {
    return doquery(1, 0, n - 1, l, r);
}

• Subtask 1: 100 / 100