Submission #197876

#	Time	Username	Problem	Language	Result	Execution time	Memory
197876		Malomalomalomalo	Secret (JOI14_secret)	C++14	0 / 100	589 ms	4600 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> a(1000 + 5);
int n;

struct node{
	node * c[2] = {nullptr, nullptr};
	int m = 0,l,r;
	vector<int> val;
	void init(int l, int r){
		this->l = l;this->r = r;	
		m = (r+l)/2;
		val = vector<int>(r-l+1);
		val[m-l] = a[m];
		for(int i = m-1;i >= l; --i){
			val[i-l] = Secret(a[i],val[i+1-l]);
		}
		val[m+1-l] = a[m+1];
		for(int i = m+2;i <= r; ++i){
			val[i-l] = Secret(a[i],val[i-1-l]);
		}
		if(r-l+1 >= 5){
			c[0] = new node();
			c[1] = new node();
			if(m-l >= 2)c[0]->init(l,m-1);
			if(r-(m+1) >= 2)c[1]->init(m+2,r);
		}
	}
	int query(int L, int R){
		if(R <= m-1){
			return c[0]->query(L,R);
		}
		else if(L >= m+2){
			return c[1]->query(L,R);
		}
		else{
			assert(l <= L && r >= R);
			if(R == m)return val[L-l];
			else if(L == m + 1)return val[R-l];
			else return Secret(val[L-l],val[R-l]);
		}
	}
} root;

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

int Query(int L, int R) {
  return (L == R ? a[L] :root.query(L,R));
}

• Subtask 1: 0 / 100