Submission #257553

#	Time	Username	Problem	Language	Result	Execution time	Memory
257553		gs18115	Secret (JOI14_secret)	C++14	100 / 100	519 ms	4748 KiB

secret

#include"secret.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
inline int f(int x,int y)
{
    return Secret(x,y);
}
vector<int>lv[4010],rv[4010];
vector<int>v;
void init(int n,int s,int e)
{
    if(s>e-2)
        return;
    int m=s+(e-s)/2;
    lv[n].eb(v[m]);
    for(int i=m;i-->s;)
        lv[n].eb(f(v[i],lv[n].back()));
    rv[n].eb(v[m+1]);
    for(int i=m+1;i++<e;)
        rv[n].eb(f(rv[n].back(),v[i]));
    init(n*2,s,m);
    init(n*2+1,m+1,e);
    return;
}
int query(int n,int s,int e,int S,int E)
{
    if(S==E)
        return v[S];
    if(S==E-1)
        return f(v[S],v[E]);
    int m=s+(e-s)/2;
    if(E<=m)
        return query(n*2,s,m,S,E);
    if(S>m)
        return query(n*2+1,m+1,e,S,E);
    return f(lv[n][m-S],rv[n][E-m-1]);
}
int n;
void Init(int N,int A[])
{
    n=N;
    for(int i=0;i<n;i++)
        v.eb(A[i]);
    init(1,0,n-1);
    return;
}
int Query(int L,int R)
{
    return query(1,0,n-1,L,R);
}

• Subtask 1: 100 / 100