Submission #540789

#	Time	Username	Problem	Language	Result	Execution time	Memory
540789		xuliu	Secret (JOI14_secret)	C++17	100 / 100	453 ms	4348 KiB

secret

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

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

const int N = 1e3, M = 10;
int dat[M][N], mask[N];
vector<int> x;

void sx(int l, int r, int lev) {
	if(l == r) return;
	int m = (l+r)/2;
	dat[lev][m] = x[m]; dat[lev][m+1] = x[m+1];
	for(int i=m-1; i>=l; i--) dat[lev][i] = Secret(x[i], dat[lev][i+1]);
	for(int i=m+2; i<=r; i++) dat[lev][i] = Secret(dat[lev][i-1], x[i]);
	for(int i=m+1; i<=r; i++) mask[i] ^= (1<<lev);
	sx(l, m, lev+1); sx(m+1, r, lev+1);
}

void Init(int n, int A[]) {
	x.assign(n, 0);
	for(int i=0; i<n; i++) x[i] = A[i];
	sx(0, n-1, 0);
}

int Query(int l, int r) {
	if(l == r) return x[l];
	int bb = __builtin_ctz(mask[l]^mask[r]);
	return Secret(dat[bb][l], dat[bb][r]);
}

• Subtask 1: 100 / 100