Submission #1135895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135895		KhoaDuy	Secret (JOI14_secret)	C++20	100 / 100	342 ms	4688 KiB

secret

#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000;
struct node{
    vector<int> pre;
    vector<int> suf;
};
node seg[4*MAXN+1];
int n;
void dnc(int v,int TL,int TR,int a[]){
    int sz=TR-TL+1;
    if(v>1&&v&1){
        seg[v].pre.resize(sz);
        seg[v].pre[0]=a[TL];
        for(int i=1;i<sz;i++){
            seg[v].pre[i]=Secret(seg[v].pre[i-1],a[i+TL]);
        }
    }
    if(v>1&&!(v&1)){
        seg[v].suf.resize(sz);
        seg[v].suf[sz-1]=a[TR];
        for(int i=sz-2;i>=0;i--){
            seg[v].suf[i]=Secret(a[i+TL],seg[v].suf[i+1]);
        }
    }
    if(TL==TR){
        if(v==1){
            seg[v].pre.resize(sz);
            seg[v].pre[0]=a[TL];
        }
        return;
    }
    int TM=((TL+TR)>>1);
    dnc(v<<1,TL,TM,a);
    dnc((v<<1)|1,TM+1,TR,a);
}
void Init(int N,int a[]){
    n=N;
    dnc(1,0,n-1,a);

}
int calc(int v,int TL,int TR,int l,int r){
    if(TL==TR){
        if(v&1){
            return seg[v].pre[0];
        }
        else{
            return seg[v].suf[0];
        }
    }
    int TM=((TL+TR)>>1);
    if(TL<=l&&r<=TM){
        return calc(v<<1,TL,TM,l,r);
    }
    else if(TM+1<=l&&r<=TR){
        return calc((v<<1)|1,TM+1,TR,l,r);
    }
    else{
        int curr=Secret(seg[v<<1].suf[l-TL],seg[(v<<1)|1].pre[r-TM-1]);
        return curr;
    }
}
int Query(int l,int r){
    return calc(1,0,n-1,l,r);
}

• Subtask 1: 100 / 100