oj.uz

Submission #233101

# Submission time Handle Problem Language Result Execution time Memory
233101 2020-05-19T10:54:04 Z PeppaPig Secret (JOI14_secret) C++14
100 / 100
 512 ms 4728 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1 << 10;

int n;
int L[N][12], R[N][12];

void Init(int _n, int A[]) {
    n = _n;

    function<void(int, int, int)> build = [&](int lvl, int l, int r) {
        if(l == r) return void(L[l][lvl] = R[l][lvl] = A[l]);

        int mid = (l + r) >> 1;
        L[mid][lvl] = A[mid], R[mid + 1][lvl] = A[mid + 1];
        for(int i = mid - 1; i >= l; i--) L[i][lvl] = Secret(A[i], L[i + 1][lvl]);
        for(int i = mid + 2; i <= r; i++) R[i][lvl] = Secret(R[i - 1][lvl], A[i]);

        build(lvl + 1, l, mid), build(lvl + 1, mid + 1, r);
    };
    build(0, 0, n - 1);
}

int Query(int x, int y) {
    function<int(int, int, int)> query = [&](int lvl, int l, int r) {
        if(l == r) return L[l][lvl];

        int mid = (l + r) >> 1;
        if(x <= mid && mid + 1 <= y) return Secret(L[x][lvl], R[y][lvl]);
        if(y <= mid) return query(lvl + 1, l, mid);
        return query(lvl + 1, mid + 1, r);
    };
    return query(0, 0, n - 1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 2552 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 146 ms 2552 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 150 ms 2556 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 504 ms 4460 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 502 ms 4472 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 509 ms 4652 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 509 ms 4728 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 512 ms 4472 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 510 ms 4568 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 504 ms 4476 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1