oj.uz

Submission #329821

# Submission time Handle Problem Language Result Execution time Memory
329821 2020-11-22T17:31:15 Z GioChkhaidze Secret (JOI14_secret) C++14
100 / 100
 511 ms 8504 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 4460 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 4460 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 143 ms 4460 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 505 ms 8300 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 507 ms 8504 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 505 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 509 ms 8428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 511 ms 8428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 505 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 505 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1