제출 #1135892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135892		KhoaDuy	비밀 (JOI14_secret)	C++20	6 / 100	349 ms	4620 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;
    seg[v].pre.resize(sz);
    seg[v].suf.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]);
    }

    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){
        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){
        return seg[v].pre[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: 6 / 100