Submission #68561

#	Time	Username	Problem	Language	Result	Execution time	Memory
68561		chpipis	Secret (JOI14_secret)	C++11	100 / 100	694 ms	8544 KiB

secret

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

using namespace std;

const int MAXN = 1005;
const int LOGN = 10;

int n, ar[MAXN];
int st[MAXN << 2][MAXN];

#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1

void build(int p, int L, int R) {
	if (L == R) return;
	housekeep;
	st[p][mid] = ar[mid];
	for (int i = mid - 1; i >= L; i--)
		st[p][i] = Secret(ar[i], st[p][i + 1]);
	st[p][mid + 1] = ar[mid + 1];
	for (int i = mid + 2; i <= R; i++)
		st[p][i] = Secret(st[p][i - 1], ar[i]);
	build(left, L, mid);
	build(right, mid + 1, R);
}

void Init(int N, int A[]) {
	n = N;
	for (int i = 0; i < n; i++)
		ar[i] = A[i];
	build(1, 0, n - 1);
}

int ask(int p, int L, int R, int i, int j) {
	housekeep;

	if (i <= mid && j >= mid + 1) {
		return Secret(st[p][i], st[p][j]);
	}

	if (j <= mid)
		return ask(left, L, mid, i, j);
	else
		return ask(right, mid + 1, R, i, j);
}

int Query(int L, int R) {
	if (L == R) return ar[L];
	return ask(1, 0, n - 1, L, R);
}

• Subtask 1: 100 / 100