Submission #1128945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128945		Nurislam	Secret (JOI14_secret)	C++17	100 / 100	425 ms	5056 KiB

secret

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

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;
	}
	
	if(l == r){
		pr[v].pb(a[l]);
		sf[v].pb(a[r]);
		return;
	}
	int m = (l+r)>>1;
	build(v*2, l, m);
	build(v*2+1, m+1, r);
	
	if(v == 1)return;
	pr[v] = pr[v*2];
	for(int i = m+1; i <= r; i++) pr[v].pb(Secret(pr[v].back(), a[i]));
	sf[v] = sf[v*2+1];
	for(int i = m; i > l; i--)   sf[v].pb(Secret(a[i], sf[v].back()));
	sf[v].pb(pr[v].back());
};
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(i > 1 && 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;
	int vl = sf[il][m - tl];
	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: 100 / 100