Submission #1128912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128912		Nurislam	Secret (JOI14_secret)	C++17	6 / 100	472 ms	5068 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
//#include "grader.cpp"

using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
int n;
vector<int> a;
vector<vector<int>> pr, sf;
void dset(){
	pr.resize(10000);
	sf.resize(10000);
};

void build(int v, int l, int r){
	if(v == 1){
		l = 0, r = n-1;
	}
	sf[v].pb(a[r]);
	for(int i = r-1; i >= l; i--){
		sf[v].pb(Secret(a[i], sf[v].back()));
	}
	pr[v].pb(a[l]);
	for(int i = l+1; i <= r; i++){
		pr[v].pb(Secret(pr[v].back(), a[i]));
	}
	
	if(l == r)return;
	int m = (l+r)>>1;
	build(v*2, l, m);
	build(v*2+1, m+1, r);
};
int ask(int i, int l, int r, int tl, int tr){
	if(i == 1){
		l = 0, r = n-1;
	}
	int m = (l+r)>>1;
	
	if(l == tl && tr == r)return pr[i].back();
	if(tr <= m)return ask(i*2, l, m, tl, tr);
	if(tl >  m)return ask(i*2+1, m+1, r, tl, tr);
	int il = i*2, ir = i*2+1;
	// sf il
	int vl = sf[il][m - tl];
	// pr ir
	int vr = pr[ir][tr - m-1];
	
	return Secret(vl, vr);
};

void Init(int N, int A[]) {
	n = N;
	for(int i = 0; i < N; i++)a.pb(A[i]);
	dset();
	build(1,1,1);
}

int Query(int l, int r) {
	return ask(1,1,1,l, r);
}

• Subtask 1: 6 / 100