Submission #1271748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271748		orzorzorz	Secret (JOI14_secret)	C++20	0 / 100	341 ms	4476 KiB

secret

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

const int MX = 1005;
int N;
int A[MX];
int leftVal[20][MX], rightVal[20][MX]; 
// 每層分治的跨越值

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

    // 往左算
    leftVal[d][mid] = A[mid];
    for (int i = mid-1; i >= l; i--)
        leftVal[d][i] = Secret(A[i], leftVal[d][i+1]);

    // 往右算
    rightVal[d][mid+1] = A[mid+1];
    for (int i = mid+2; i <= r; i++)
        rightVal[d][i] = Secret(rightVal[d][i-1], A[i]);

    build(l, mid, d+1);
    build(mid+1, r, d+1);
}

void Init(int n, int a[]) {
    N = n;
    for (int i = 0; i < N; i++) A[i] = a[i];
    build(0, N-1, 0);
}

int query(int l, int r, int ql, int qr, int d) {
    if (ql <= l && r <= qr) {
        // fully inside
        return -1; // 不直接回，因為要判斷跨不跨
    }
    int mid = (l + r) / 2;
    if (qr <= mid) return query(l, mid, ql, qr, d+1);
    if (ql > mid) return query(mid+1, r, ql, qr, d+1);

    // 跨越區間
    return Secret(leftVal[d][ql], rightVal[d][qr]);
}

int Query(int L, int R) {
    return query(0, N-1, L, R, 0);
}

• Subtask 1: 0 / 100