Submission #1135877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135877		nathan4690	Secret (JOI14_secret)	C++20	100 / 100	345 ms	16296 KiB

secret

#include "secret.h"

int n, a[10005];
int pf[4005][1005], sf[4005][1005];
void build(int idx, int l, int r){
    if(l == r){
        pf[idx][l] = sf[idx][l] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    sf[idx*2][mid] = a[mid];
    for(int i=mid-1;i>=l;i--) sf[idx*2][i] = Secret(a[i], sf[idx*2][i+1]);
    pf[idx*2+1][mid+1] = a[mid+1];
    for(int i=mid+2;i<=r;i++) pf[idx*2+1][i] = Secret(pf[idx*2+1][i-1], a[i]);
    build(idx*2, l, mid);
    build(idx*2+1, mid+1, r);
//    if(l == 0 && r == n-1) return;
//    for(int i=l;i<=mid;i++) pf[idx][i] = pf[idx*2][i];
//    for(int i=mid+1;i<=r;i++) pf[idx][i] = Secret(pf[idx][i-1], a[i]);
//    for(int i=r;i>=mid+1;i--) sf[idx][i] = sf[idx*2+1][i];
//    for(int i=mid;i>=l;i--) sf[idx][i] = Secret(a[i], sf[idx][i+1]);
}

int getRange(int idx, int l, int r, int u, int v){
    int mid = (l + r) / 2;
    if(v <= mid) return getRange(idx*2, l, mid, u, v);
    if(mid < u) return getRange(idx*2+1, mid+1, r, u, v);
    return Secret(sf[idx*2][u], pf[idx*2+1][v]);
}

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

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

• Subtask 1: 100 / 100