Submission #329821

#	Time	Username	Problem	Language	Result	Execution time	Memory
329821		GioChkhaidze	Secret (JOI14_secret)	C++14	100 / 100	511 ms	8504 KiB

secret

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

#define ll long long

using namespace std;

const int M=1e3+5;

int n,a[M],ans[M][M];

void Go(int l,int r) {
	if (r-l<2) return ;
	
	int mid=(l+r)/2;

	// left segment l...mid
  // right segment mid+1...r

	for (int i=mid-1; i>=l; i--) 
		ans[i][mid]=Secret(a[i],ans[i+1][mid]);

 	for (int i=mid+2; i<=r; i++)
		ans[mid+1][i]=Secret(ans[mid+1][i-1],a[i]);
  	
	Go(l,mid);
	Go(mid+1,r);	
}

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

int ansL,ansR;
int Get(int l,int r) {
	if (r-l<2) return 0;
	if (!(l<=ansL && ansR<=r)) return 0;
	int mid=(l+r)/2;
	
	if (ansL<=mid && mid+1<=ansR) {
		return Secret(ans[ansL][mid],ans[mid+1][ansR]);
	}

	return Get(l,mid)+Get(mid+1,r);		
}

int Query(int L, int R) {
	if (L==R) return ans[L][R];
	if (R-L==1) return Secret(a[L],a[R]);

	ansL=L,ansR=R;
	return Get(0,n-1);
}

• Subtask 1: 100 / 100