Submission #540787

#	Time	Username	Problem	Language	Result	Execution time	Memory
540787		Runtime_error_	Secret (JOI14_secret)	C++14	100 / 100	454 ms	4636 KiB

secret

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

int a[1111];
int n;
vector<int> pre[4444];
vector<int> suf[4444];
void build(int p,int s,int e)
{
    if(s==e){
        suf[p].push_back(a[s]);
        return;
    }
    int mid=(s+e)/2;
    build(p*2,s,mid);
    build(p*2+1,mid+1,e);
    pre[p].push_back(a[mid+1]);
    for(int i=mid+2;i<=e;i++){
        pre[p].push_back(Secret(pre[p].back(),a[i]));
    }
    suf[p].push_back(a[mid]);
    for(int i=mid-1;i>=s;i--){
        suf[p].push_back(Secret(a[i],suf[p].back()));
    }
}
int get(int p,int s,int e,int a,int b)
{
    int mid=(s+e)/2;
    if(a<=mid&&mid<=b){
        if(b==mid){
            int h=mid-a;
            return suf[p][h];
        }
        else{
            int h=mid-a;
            int h2=b-(mid+1);
            return Secret(suf[p][h],pre[p][h2]);
        }
    }
    if(b<=mid){
        return get(p*2,s,mid,a,b);
    }
    else{
        return get(p*2+1,mid+1,e,a,b);
    }
}
void Init(int N, int A[]){
    n=N;
    for(int i=0;i<n;i++){
        a[i]=A[i];
    }
    build(1,0,n-1);
}

int Query(int L, int R) {
    return get(1,0,n-1,L,R);
}

• Subtask 1: 100 / 100