oj.uz

Submission #407432

# Submission time Handle Problem Language Result Execution time Memory
407432 2021-05-19T00:13:22 Z smax Secret (JOI14_secret) C++17
100 / 100
 535 ms 4468 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 2372 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 145 ms 2400 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 2456 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 499 ms 4420 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 528 ms 4340 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 535 ms 4400 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 516 ms 4468 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 509 ms 4296 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 518 ms 4280 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 521 ms 4292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1