Submission #1128902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128902		Nurislam	Secret (JOI14_secret)	C++17	0 / 100	451 ms	4816 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(8000);
		sf.resize(8000);
	};
	
	void build(int v, int l, int r){
		if(v == 1){
			l = 0, r = n-1;
		}
		pr[v].pb(a[l]);
		for(int i = l+1; i <= r; i++){
			pr[v].pb(Secret(pr[v].back(), a[i]));
		}
		sf[v].pb(a[r]);
		for(int i = r-1; i >= l; i--){
			sf[v].pb(Secret(sf[v].back(), a[i]));
		}
		reverse(all(sf));
		if(l == r)return;
		
		int m = (l+r)>>1;
		build(v*2, l, m);
		build(v*2, 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(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];
		
		return Secret(vl, vr);
	};

void Init(int N, int A[]) {
	n = N;
	vector<int> a;
	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: 0 / 100