Submission #1304119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304119		Warinchai	Secret (JOI14_secret)	C++20	100 / 100	335 ms	4464 KiB

secret

#include "secret.h"
#include<bits/stdc++.h>
using namespace std;

int ans[15][1005];
int val[1005];
int n;

struct seg{
    void build(int st,int en,int lv){
        int m=(st+en)/2;
        ans[lv][m]=val[m];
        if(st==en)return;
        for(int i=m-1;i>=st;i--)ans[lv][i]=Secret(val[i],ans[lv][i+1]);
        ans[lv][m+1]=val[m+1];
        for(int i=m+2;i<=en;i++)ans[lv][i]=Secret(ans[lv][i-1],val[i]);
        //cerr<<"build:"<<st<<" "<<en<<"\n";
        //for(int i=st;i<=en;i++)cerr<<ans[lv][i]<<" ";
        //cerr<<"\n";
        build(st,m,lv+1);
        build(m+1,en,lv+1);
    }
    int fans(int st,int en,int l,int r,int lv){
        int m=(st+en)/2;
        if(st==en){
            //cerr<<"st,en:"<<l<<" "<<m<<" "<<r<<" "<<val[st]<<"\n";
            return val[st];
        }
        if(r<=m)return fans(st,m,l,r,lv+1);
        else if(l>=m+1)return fans(m+1,en,l,r,lv+1);
        else{
            //cerr<<"st,en:"<<l<<" "<<m<<" "<<r<<" "<<ans[lv][l]<<" "<<ans[lv][r]<<"\n";
            return Secret(ans[lv][l],ans[lv][r]);
        }
    }
}tr;

void Init(int N, int A[]) {
    n=N;
    for(int i=0;i<=10;i++)for(int j=0;j<=n+1;j++)ans[i][j]=0;
    for(int i=1;i<=n;i++)val[i]=A[i-1];
    tr.build(1,n,1);
}

int Query(int L, int R) {
    //cerr<<"QR:"<<L+1<<" "<<R+1<<"\n";
    return tr.fans(1,n,L+1,R+1,1);
}

• Subtask 1: 100 / 100