Submission #407432

#	Time	Username	Problem	Language	Result	Execution time	Memory
407432		smax	Secret (JOI14_secret)	C++17	100 / 100	535 ms	4468 KiB

secret

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

int n;
vector<vector<int>> prod;

void Init(int N, int A[]) {
    auto recur = [&] (auto &self, int lg, int l, int r) -> void {
        if (lg == (int) prod.size())
            prod.emplace_back(N);
        if (l == r) {
            prod[lg][l] = A[l];
            return;
        }
        int m = (l + r) / 2;
        prod[lg][m] = A[m];
        for (int i=m-1; i>=l; i--)
            prod[lg][i] = Secret(A[i], prod[lg][i+1]);
        prod[lg][m+1] = A[m+1];
        for (int i=m+2; i<=r; i++)
            prod[lg][i] = Secret(prod[lg][i-1], A[i]);
        self(self, lg + 1, l, m);
        self(self, lg + 1, m + 1, r);
    };

    n = N;
    prod.clear();
    recur(recur, 0, 0, N - 1);
}

int Query(int L, int R) {
    auto recur = [&] (auto &self, int lg, int l, int r) -> int {
        if (l == r)
            return prod[lg][l];
        int m = (l + r) / 2;
        if (L <= m && m < R)
            return Secret(prod[lg][L], prod[lg][R]);
        if (L <= m && R <= m)
            return self(self, lg + 1, l, m);
        return self(self, lg + 1, m + 1, r);
    };

    return recur(recur, 0, 0, n - 1);
}

• Subtask 1: 100 / 100