제출 #1271751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271751		orzorzorz	비밀 (JOI14_secret)	C++20	100 / 100	344 ms	4468 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN = 1005;

int n;
int c[mxN];
int g[mxN][20]; // g[i][k]：在第 k 層分治時，i 點對應的累積值

void dc(int l, int r, int k) {
    if (l == r) return;
    int mid = (l + r) / 2;

    // 左邊累積
    g[mid][k] = c[mid];
    for (int i = mid - 1; i >= l; i--) {
        g[i][k] = Secret(c[i], g[i + 1][k]);
    }

    // 右邊累積
    g[mid + 1][k] = c[mid + 1];
    for (int i = mid + 2; i <= r; i++) {
        g[i][k] = Secret(g[i - 1][k], c[i]);
    }

    dc(l, mid, k + 1);
    dc(mid + 1, r, k + 1);
}

void Init(int N, int A[]) {
    n = N;
    for (int i = 0; i < N; i++) c[i] = A[i];
    dc(0, n - 1, 0); // 從第 0 層開始
}

int qry(int k, int l, int r, int L, int R) {
    int mid = (L + R) / 2;
    if (l <= mid && r > mid) {
        return Secret(g[l][k], g[r][k]);
    }
    if (r <= mid) return qry(k + 1, l, r, L, mid);
    if (l > mid) return qry(k + 1, l, r, mid + 1, R);
    return -1; // safety
}

int Query(int L, int R) {
    if (L == R) return c[L];
    return qry(0, L, R, 0, n - 1);
}

• Subtask 1: 100 / 100