Submission #56555

#	Time	Username	Problem	Language	Result	Execution time	Memory
56555		Bruteforceman	비밀 (JOI14_secret)	C++11	100 / 100	746 ms	5412 KiB

secret

#include "secret.h"
#include "bits/stdc++.h"
using namespace std;
map <int, int> v[1100 * 4];
int a[1100];
int n;

void solve(int c, int b, int e) {
	if(b == e) {
		v[c][b] = a[b];
		return ;
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	solve(l, b, m);
	solve(r, m+1, e);
	if(c == 1) {
		return ;
 	}
	if(c & 1) {
		v[c][b] = a[b];
		for(int i = b + 1; i <= e; i++) {
			v[c][i] = Secret(v[c][i - 1], a[i]);
		}
	} else {
		v[c][e] = a[e];
		for(int i = e - 1; i >= b; i--) {
			v[c][i] = Secret(a[i], v[c][i + 1]);
		}
	}
}

int answer(int x, int y, int c, int b, int e) {
	if(b == e) {
		return a[b];
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(y <= m) {
		return answer(x, y, l, b, m);
	} else if (m < x) {
		return answer(x, y, r, m+1, e);
	} else {
		return Secret(v[l][x], v[r][y]); 
	}
}
void Init(int N, int A[]) {
	for(int i = 0; i < N; i++) {
		a[i] = A[i];
	}
	solve(1, 0, N-1);
	n = N;
}
int Query(int L, int R) {
  return answer(L, R, 1, 0, n-1);
}

• Subtask 1: 100 / 100