제출 #1196959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196959		og_matveychick1	비밀 (JOI14_secret)	C++20	100 / 100	343 ms	8288 KiB

secret

#include "secret.h"

const int N = 1e3;

int n, a[N], b[N][N];

void go(int l, int r) {
    if (l + 1 == r) return;
    int m = (l + r) / 2;
    b[m][m] = a[m];
    b[m - 1][m - 1] = a[m - 1];
    for (int i = m - 2; i >= l; i--) b[i][m - 1] = Secret(a[i], b[i + 1][m - 1]);
    for (int i = m + 1; i < r; i++) {
        b[m][i] = Secret(b[m][i - 1], a[i]);
    }
    go(l, m), go(m, r);
}

void Init(int _n, int A[]) {
    n = _n;
    for (int i = 0; i < n; i++) a[i] = A[i];
    go(0, n);
}

int get(int l, int r, int L, int R) {
    int m = (l + r) / 2;
    if (m == L || m == R) return b[L][R - 1];
    if (m <= L) return get(m, r, L, R);
    else if (m >= R) return get(l, m, L, R);
    return Secret(b[L][m - 1], b[m][R - 1]);
}

int Query(int L, int R) {
    return get(0, n, L, R + 1);
}

• Subtask 1: 100 / 100