Submission #321637

#	Time	Username	Problem	Language	Result	Execution time	Memory
321637		peuch	Secret (JOI14_secret)	C++17	0 / 100	514 ms	9868 KiB

secret

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

const int MAXN = 1010;

int n;
long long value[MAXN][MAXN];
long long v[MAXN];

void dc(int ini, int fim){
	if(ini == fim) {
		value[ini][ini] = v[ini];
		return;
	}
	int mid = (ini + fim) / 2;

	dc(ini, mid);
	dc(mid + 1, fim);

	value[mid][mid] = v[mid];
	for(int i = mid - 1; i >= ini; i--)
		value[i][mid] = Secret(value[i + 1][mid], v[i]);

	value[mid + 1][mid + 1] = v[mid + 1];
	for(int i = mid + 2; i <= fim; i++)
		value[mid + 1][i] = Secret(value[mid + 1][i - 1], v[i]);
}

long long getVal(int ini, int fim, int l, int r){
	// printf("\t%d %d\n", ini, fim);
	if(ini == fim) return value[ini][ini];
	int mid = (ini + fim) / 2;
	if(l <= mid && r > mid)
		return Secret(value[l][mid], value[mid + 1][r]);
	if(r <= mid)
		return getVal(ini, mid, l, r);
	return getVal(mid + 1, fim, l, r);
}

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

int Query(int L, int R) {
	// printf("Query: %d %d\n", L, R);
	if(L == R) return v[L];
	return getVal(0, n - 1, L, R);
}

//g++ -o secret -O2 grader.cpp secret.cpp

• Subtask 1: 0 / 100