제출 #1158930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158930		AlgorithmWarrior	비밀 (JOI14_secret)	C++20	100 / 100	341 ms	4460 KiB

secret

#include "secret.h"

#include <bits/stdc++.h>

int precalc[1005][13];
int v[1005];

void do_precalc(int st,int dr,int niv){
    if(st<dr){
        int mij=(st+dr)/2;
        int i;
        precalc[mij][niv]=v[mij];
        for(i=mij-1;i>=st;--i)
            precalc[i][niv]=Secret(v[i],precalc[i+1][niv]);
        precalc[mij+1][niv]=v[mij+1];
        for(i=mij+2;i<=dr;++i)
            precalc[i][niv]=Secret(precalc[i-1][niv],v[i]);
        do_precalc(st,mij,niv+1);
        do_precalc(mij+1,dr,niv+1);
    }
}

int n;

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

int solve(int st,int dr,int niv,int l,int r){
    int mij=(st+dr)/2;
    if(l<=mij && mij<r)
        return Secret(precalc[l][niv],precalc[r][niv]);
    if(r<=mij)
        return solve(st,mij,niv+1,l,r);
    else
        return solve(mij+1,dr,niv+1,l,r);
}

int Query(int L, int R) {
    if(L==R)
        return v[L];
    else
        return solve(0,n-1,0,L,R);
}

• Subtask 1: 100 / 100