Submission #924719

#	Time	Username	Problem	Language	Result	Execution time	Memory
924719		Hakiers	Secret (JOI14_secret)	C++17	100 / 100	393 ms	8528 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
constexpr int MAXN = 1e3 + 7;
int interval[MAXN][MAXN];
int input[MAXN];
int n;

void dpc(int l, int r){
	if(r < l) return;
	
	int mid = (l+r)/2;
	//cout << "mid" << mid << " " << l << " " << r << "\n";
	
	for(int i = mid - 1; i >= l; i--){
		interval[mid][i] = Secret(input[i], interval[mid][i+1]);
		//cout << i << " " << mid << " " << interval[mid][i] << "\n";
	}	
	
	
	if(mid+1 < n) interval[mid][mid+1] = input[mid+1];
	for(int i = mid+2; i <= r; i++)
		interval[mid][i] = Secret(interval[mid][i-1], input[i]);
	
	dpc(l, mid-1);
	dpc(mid+1, r);	
}

int dpcQ(int l, int r, int a, int b){
	int mid = (l+r)/2;
	
	if(a <= mid && mid <= b){
		//cout << "mid" << mid << "\n";
		if(b == mid) return interval[mid][a];
		return Secret(interval[mid][a], interval[mid][b]); 
	}
	else if(b < mid)
		return dpcQ(l, mid-1, a, b);
	else return dpcQ(mid+1, r, a, b);	
}


void Init(int N, int A[]) {
  //Secret(0, 1000000000);
  n = N;
  for(int i = 0; i < n; i++){
  	input[i] = A[i];
  	interval[i][i] = A[i];
  }
 
  dpc(0, n-1);
  
}

int Query(int L, int R) {
  	return dpcQ(0, n-1, L, R);
}

• Subtask 1: 100 / 100