Submission #1013153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013153		Pannda	Secret (JOI14_secret)	C++17	100 / 100	304 ms	8540 KiB

secret

#include "secret.h"

#include <bits/stdc++.h>
using namespace std;

namespace {
    const int n = 1000;
    vector<int> a(n, 0);
    vector<vector<int>> tree(4 * n);
}

void Init(int N, int A[]) {
    copy(A, A + N, a.begin());
    auto build = [&](auto self, int idx, int l, int r) -> void {
        if (l + 1 == r) {
            tree[idx] = {a[l]};
            return;
        }
        int m = (l + r) >> 1;
        self(self, 2 * idx + 1, l, m);
        self(self, 2 * idx + 2, m, r);
        tree[idx].resize(n, -1);
        tree[idx][m - 1] = a[m - 1];
        for (int i = m - 2; i >= l; i--) {
            tree[idx][i] = Secret(a[i], tree[idx][i + 1]);
        }
        tree[idx][m] = a[m];
        for (int i = m + 1; i < r; i++) {
            tree[idx][i] = Secret(tree[idx][i - 1], a[i]);
        }
    };
    build(build, 0, 0, n);
}

int Query(int ql, int qr) {
    qr++;
    int idx = 0, l = 0, r = n;
    while (true) {
        if (l + 1 == r) return a[l];
        int m = (l + r) >> 1;
        if (l <= ql && qr <= m) {
            r = m;
            idx = 2 * idx + 1;
            continue;
        }
        if (m <= ql && qr <= r) {
            l = m;
            idx = 2 * idx + 2;
            continue;
        }
        return Secret(tree[idx][ql], tree[idx][qr - 1]);
    }
}

• Subtask 1: 100 / 100