Submission #257553

# Submission time Handle Problem Language Result Execution time Memory
257553 2020-08-04T12:00:22 Z gs18115 Secret (JOI14_secret) C++14
100 / 100
519 ms 4748 KB
#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);
}
# Verdict Execution time Memory Grader output
1 Correct 144 ms 2680 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 2680 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 147 ms 2648 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 510 ms 4728 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 513 ms 4676 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 509 ms 4732 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 512 ms 4640 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 519 ms 4728 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 510 ms 4748 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 509 ms 4688 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1