Submission #479159

#	Time	Username	Problem	Language	Result	Execution time	Memory
479159		Urvuk3	Secret (JOI14_secret)	C++17	100 / 100	530 ms	9036 KiB

secret

#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 / 100