oj.uz

Submission #479159

# Submission time Handle Problem Language Result Execution time Memory
479159 2021-10-10T10:23:20 Z Urvuk3 Secret (JOI14_secret) C++17
100 / 100
 530 ms 9036 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll MAXN=3005,MAXA=5e6+5,INF=1e9,LINF=1e18;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mid (l+r)/2
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define mod 1000000007LL
#define pb push_back
#define endl "\n"
#define PRINT(x) cerr<<#x<<'-'<<x<<endl<<flush;
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
#define PRINTvec(x) { cerr<<#x<<"-"; for(int i=0;i<sz(x);i++) cerr<<x[i]<<" "; cerr<<endl; }
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

vector<int> a;
int st[MAXN][MAXN];
ll n;

void init(int l,int r){
    if(l==r) return;
    for(int i=mid-1;i>=l;i--){
        st[i][mid]=Secret(a[i],st[i+1][mid]);
    }
    for(int i=mid+2;i<=r;i++){
        st[mid+1][i]=Secret(st[mid+1][i-1],a[i]);
    }
    init(l,mid);
    init(mid+1,r);
}

void Init(int N, int A[]){
    n=N;
    a.resize(n+1);
    for(int i=0;i<n;i++){
        a[i+1]=A[i];
    }
    for(int i=1;i<=n;i++){
        st[i][i]=a[i];
    }
    init(1,n);
}

int query(int l,int r,int L,int R){
    if(l==r) return a[l];
    if(L<=mid && R>mid) return Secret(st[L][mid],st[mid+1][R]);
    if(R<=mid) return query(l,mid,L,R);
    return query(mid+1,r,L,R);
}

int Query(int L,int R){
    return query(1,n,L+1,R+1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 4624 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 140 ms 4676 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 4596 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 530 ms 9032 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 499 ms 8968 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 520 ms 9016 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 497 ms 8988 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 492 ms 9028 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 509 ms 9024 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 508 ms 9036 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1