Submission #134322

#	Time	Username	Problem	Language	Result	Execution time	Memory
134322		someone_aa	Secret (JOI14_secret)	C++17	100 / 100	618 ms	12604 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1100;
int prefix[maxn][maxn];
int suffix[maxn][maxn];
int arr[maxn], n;

void precompute(int l, int r) {
	if(l > r) return;
	if(l == r) return;
	else {
		int mid = (l + r) / 2;

		//cout<<mid<<" ";

		suffix[mid][mid] = arr[mid];
		prefix[mid][mid+1] = arr[mid+1];

		for(int i=mid-1;i>=l;i--) {
			suffix[mid][i] = Secret(arr[i], suffix[mid][i+1]);
		}

		for(int i=mid+2;i<=r;i++) {
			prefix[mid][i] = Secret(prefix[mid][i-1], arr[i]);
		}

		precompute(l, mid);
		precompute(mid+1,r);
	}
}

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

int solve(int ql, int qr, int li=0, int ri=n-1) {
	if(li == ri) return arr[li];
	else {
		int mid = (li + ri) / 2;

		if(ql <= mid && qr > mid) {
			//cout<<"Here: ["<<li<<", "<<ri<<"] - ";
			//cout<<suffix[mid][ql]<<" "<<prefix[mid][qr]<<"\n";
			return Secret(suffix[mid][ql], prefix[mid][qr]);
		}
		else if(qr <= mid) {
			return solve(ql, qr, li, mid);
		}
		else {
			return solve(ql, qr, mid+1, ri);
		}
	}
}

int Query(int L, int R) {
  	return solve(L, R);
}

• Subtask 1: 100 / 100