oj.uz

Submission #492422

# Submission time Handle Problem Language Result Execution time Memory
492422 2021-12-07T09:08:09 Z alextodoran Secret (JOI14_secret) C++17
100 / 100
 443 ms 4576 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;

typedef long long ll;

const int N_MAX = 1000;
const int LOG2_MAX = 10;

int Secret (int X, int Y);

int N;

int A[N_MAX];

int sum[LOG2_MAX][N_MAX];

void buildSums (int L = 0, int R = N - 1, int depth = 0) {
    if (L == R) {
        return;
    }

    int mid = (L + R) / 2;
    int l1 = L, r1 = mid;
    int l2 = mid + 1, r2 = R;

    sum[depth][r1] = A[r1];
    for (int i = r1 - 1; i >= l1; i--) {
        sum[depth][i] = Secret(A[i], sum[depth][i + 1]);
    }
    sum[depth][l2] = A[l2];
    for (int i = l2 + 1; i <= r2; i++) {
        sum[depth][i] = Secret(sum[depth][i - 1], A[i]);
    }

    buildSums(l1, r1, depth + 1);
    buildSums(l2, r2, depth + 1);
}

void Init (int _N, int _A[]) {
    N = _N;
    for (int i = 0; i < N; i++) {
        A[i] = _A[i];
    }
    buildSums();
}

int getSum (int ql, int qr, int L = 0, int R = N - 1, int depth = 0) {
    if (L == R) {
        return A[L];
    }

    int mid = (L + R) / 2;
    int l1 = L, r1 = mid;
    int l2 = mid + 1, r2 = R;

    if (ql <= r1 && l2 <= qr) {
        return Secret(sum[depth][ql], sum[depth][qr]);
    } else if (qr <= r1) {
        return getSum(ql, qr, l1, r1, depth + 1);
    } else {
        return getSum(ql, qr, l2, r2, depth + 1);
    }
}

int Query (int L, int R) {
    return getSum(L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 2460 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 123 ms 2368 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 137 ms 2412 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 436 ms 4400 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 439 ms 4420 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 439 ms 4396 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 443 ms 4360 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 435 ms 4576 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 435 ms 4344 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 430 ms 4392 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1