제출 #1357558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1357558		tuongll	비밀 (JOI14_secret)	C++20	100 / 100	301 ms	8336 KiB

secret

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

const int N = 1e3 + 3;

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

void peqingduck(int l, int r){
    if (l == r){
        f[l][r] = a[l];
        return;
    }

    int mid = (l + r) / 2;
    f[mid][mid] = a[mid];
    f[mid + 1][mid + 1] = a[mid + 1];

    for (int i = mid + 2; i <= r; ++i)
        f[mid + 1][i] = Secret(f[mid + 1][i - 1], a[i]);
    for (int i = mid - 1; i >= l; --i)
        f[i][mid] = Secret(a[i], f[i + 1][mid]);

    peqingduck(l, mid);
    peqingduck(mid + 1, r);
}

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

int get(int l, int r, int u, int v){
    if (l == r) return a[l];

    int mid = (l + r) / 2;
    if (v <= mid) return get(l, mid, u, v);
    else if (u > mid) return get(mid + 1, r, u, v);
    else return Secret(f[u][mid], f[mid + 1][v]);
}

int Query(int l, int r){
    return get(0, n - 1, l, r);
}

• Subtask 1: 100 / 100