Submission #112867

#	Time	Username	Problem	Language	Result	Execution time	Memory
112867		Anai	Secret (JOI14_secret)	C++14	100 / 100	516 ms	4696 KiB

secret

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

const int N = 1005;

vector<int> pom[N * 4];
int v[N];

int n, ql, qr;


static inline void build(int nod, int st, int dr) {
	if (st == dr) {
		pom[nod] = {v[st]};
		return; }
	int mid = (st + dr) / 2;

	build(2 * nod, st, mid);
	build(2 * nod + 1, mid + 1, dr);

	pom[nod].resize(dr - st + 1);
	pom[nod][mid - st] = v[mid];
	pom[nod][mid + 1 - st] = v[mid + 1];
	for (int i = mid + 2; i <= dr; ++i)
		pom[nod][i - st] = Secret(pom[nod][i - 1 - st], v[i]);
	for (int i = mid - 1; i >= st; --i)
		pom[nod][i - st] = Secret(v[i], pom[nod][i + 1 - st]); }

static int query(int nod, int st, int dr) {
	if (ql == qr)
		return v[ql];
	int mid = (st + dr) / 2;
	if (ql <= mid && mid < qr)
		return Secret(pom[nod][ql - st], pom[nod][qr - st]);
	if (qr <= mid)
		return query(2 * nod, st, mid);
	else
		return query(2 * nod + 1, mid + 1, dr); }

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

int Query(int L, int R) {
	ql = L, qr = R;
	return query(1, 0, n - 1); }

• Subtask 1: 100 / 100