Submission #642049

#	Time	Username	Problem	Language	Result	Execution time	Memory
642049		ymm	Secret (JOI14_secret)	C++17	100 / 100	489 ms	12432 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

static int n, *a;
static int seg[5010][2010];

static void init(int i, int b, int e)
{
	if (e-b == 1) {
		seg[i][b] = a[b];
		return;
	}
	int m = (b+e)/2;
	init(2*i+1, b, m);
	init(2*i+2, m, e);
	seg[i][m] = a[m];
	Loop (j,m+1,e)
		seg[i][j] = Secret(seg[i][j-1], a[j]);
	seg[i][m-1] = a[m-1];
	LoopR (j,b,m-1)
		seg[i][j] = Secret(a[j], seg[i][j+1]);
}

void Init(int N, int A[]) {
	n = N; a = A;
	init(0, 0, n);
}

static int query(int l, int r, int i, int b, int e)
{
	int m = (b+e)/2;
	if (l <= m && m <= r) {
		if (m == r)
			return seg[i][l];
		if (m == l)
			return seg[i][r-1];
		return Secret(seg[i][l], seg[i][r-1]);
	}
	if (r < m)
		return query(l, r, 2*i+1, b, m);
	else
		return query(l, r, 2*i+2, m, e);
}

int Query(int L, int R) {
	return query(L, R+1, 0, 0, n);
}

• Subtask 1: 100 / 100