Submission #492422

#	Time	Username	Problem	Language	Result	Execution time	Memory
492422		alextodoran	Secret (JOI14_secret)	C++17	100 / 100	443 ms	4576 KiB

secret

/**
 ____ ____ ____ ____ ____
||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 / 100