제출 #1256693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256693		nguyenhuythach	비밀 (JOI14_secret)	C++20	0 / 100	355 ms	4508 KiB

secret

#include "secret.h"
#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=1069;
int n;
int a[nmax],pfx[15][nmax],suf[15][nmax];

void dnc(int l,int r,int lv)
{
    if(l==r)
    {
        suf[lv][l]=a[l];
        return;
    }
    int mid=(l+r)/2;
    
    //precase
    suf[lv][mid]=a[mid];
    pfx[lv][mid+1]=a[mid+1];
    
    //build
    REP(i,mid-1,l) suf[lv][i]=Secret(a[i],suf[lv][i+1]);
    FOR(i,mid+2,r) pfx[lv][i]=Secret(pfx[lv][i-1],a[i]);
    
    //recursion
    dnc(l,mid,lv+1);
    dnc(mid+1,r,lv+1);
}

void Init(int N, int A[])
{
    n=N;
    FOR(i,1,n) a[i]=A[i-1];
    dnc(1,n,1);
}

pii find(int l,int r,int lv,int lf,int rt)
{
    int mid=(l+r)/2;
    if(l<=lf && rt<=r && lf<=mid && mid<=rt) return {lv,mid};
    if(l<=lf && rt<=mid) return find(l,mid,lv+1,lf,rt);
    else return find(mid+1,r,lv+1,lf,rt);
}

int Query(int L,int R)
{
    int l=L+1,r=R+1;
    auto save=find(1,n,1,l,r);
    if(l==r) return a[l];
    else if(r==save.se) return suf[save.fi][l];
    else if(l==save.se) return pfx[save.fi][r];
    else return Secret(suf[save.fi][l],pfx[save.fi][r]);
}

• Subtask 1: 0 / 100