Submission #1208215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208215		edga1	Secret (JOI14_secret)	C++20	100 / 100	347 ms	4560 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

vector<int> st[2500];
int a[1005];
int n;

void build(int x, int xl, int xr, int v){
    if(v!=0){
        if(v==1) st[x].pb(a[xl]);
        else st[x].pb(a[xr]);
        for(int i=1; i<=xr-xl; i++){
            if(v==1) st[x].pb(Secret(st[x][st[x].size()-1],a[xl+i]));
            else st[x].pb(Secret(a[xr-i],st[x][st[x].size()-1]));
        }
    }
    if(xl==xr) return;
    int mid=(xl+xr)/2;
    build(x*2+1,xl,mid,-1);
    build(x*2+2,mid+1,xr,1);
}

int get(int x, int xl, int xr, int l, int r){
    if(xl==xr) return a[xl];
    int mid=(xl+xr)/2;
    if(mid>r) return get(x*2+1,xl,mid,l,r);
    if(mid<l) return get(x*2+2,mid+1,xr,l,r);
    if(mid-l<0) return st[x*2+2][r-mid-1];
    if(r-mid-1<0) return st[x*2+1][mid-l];
    int r1=st[x*2+1][mid-l], r2=st[x*2+2][r-mid-1];
    return Secret(r1,r2);
}

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

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

• Subtask 1: 100 / 100