Submission #628241

#	Time	Username	Problem	Language	Result	Execution time	Memory
628241		I_am_balancing	Secret (JOI14_secret)	C++17	100 / 100	465 ms	4420 KiB

secret

#include "secret.h"

using ll = long long;
int val[12][1005], a[1005], n;

void precalc(ll l, ll r, ll la){
    ll m = (l+r)>>1;
    if(l > r)return;
    val[la][m] = a[m];
    if(l == r)return;
    if(l<=m-1)val[la][m-1] = a[m-1];
    for(ll i = m+1;i<=r;i++)val[la][i]=Secret(val[la][i-1],a[i]);
    for(ll i = m-2;i>=l;i--)val[la][i]=Secret(a[i],val[la][i+1]);
    precalc(l,m-1,la+1);
    precalc(m+1,r,la+1);
}

void Init(int N, int A[]){
    for(ll i = 0;i<N;i++)a[i] = A[i];
    precalc(0,N-1,0);
    n = N;
}
int query(int L, int R, ll l, ll r, ll la){
    ll m = (l+r)>>1;
    if(L <= m && m <= R){
        if(L!=m)
        return Secret(val[la][L],val[la][R]);
        return val[la][R];
    }
    if(m > L)return query(L,R,l,m-1,la+1);
    return query(L,R,m+1,r,la+1);
}

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

• Subtask 1: 100 / 100