Submission #29099

#	Time	Username	Problem	Language	Result	Execution time	Memory
29099		cdemirer	Secret (JOI14_secret)	C++14	30 / 100	703 ms	6036 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int _N;

typedef struct NodeTag {
	int llim, rlim;
	int value;
} Node;
const int segsz = 2048;
Node seg[segsz];
int offset = segsz / 2;
#define left(x) ((x)*2)
#define right(x) ((x)*2+1)
#define parent(x) ((x)/2)

int combineval(int a, int b) {
	if (a == -1) return -1;
	if (b == -1) return a;
	return Secret(a, b);
}
int combine(int a, int b) {
	return combineval(seg[a].value, seg[b].value);
}

int get(int x, int l, int r) {
	int llim = seg[x].llim;
	int rlim = seg[x].rlim;
	int mid = (llim + rlim) / 2;
	if (l == llim && r == rlim) return seg[x].value;
	else if (l > mid) return get(right(x), l, r);
	else if (r <= mid) return get(left(x), l, r);
	else {
		int a = get(left(x), l, mid);
		int b = get(right(x), mid+1, r);
		return combineval(a, b);
	}
}

void Init(int N, int A[]) {
	_N = N;
	for (int i = offset; i < segsz; i++) {
		seg[i].llim = seg[i].rlim = i-offset;
		seg[i].value = -1;
		if (i-offset < N) seg[i].value = A[i-offset];
	}
	for (int i = offset-1; i > 0; i--) {
		seg[i].llim = seg[left(i)].llim;
		seg[i].rlim = seg[right(i)].rlim;
		seg[i].value = combine(left(i), right(i));
	}
}

int Query(int L, int R) {
	return get(1, L, R);
}

• Subtask 1: 30 / 100