oj.uz

Submission #434943

# Submission time Handle Problem Language Result Execution time Memory
434943 2021-06-22T12:12:43 Z keta_tsimakuridze Secret (JOI14_secret) C++14
100 / 100
 573 ms 8280 KB 
#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
int x[1005][1005],a[1005],n;
void solve(int l,int r) {
	if(l==r) return;
	int mid = (l+r)/2; 
	x[mid][mid] = a[mid];
	for(int i=mid-1;i>=l;i--) {
		x[i][mid] = Secret(a[i],x[i+1][mid]);
	}
	
	x[mid+1][mid+1]=a[mid+1];
	for(int i=mid+2;i<=r;i++) {
		x[mid+1][i] = Secret(x[mid+1][i-1],a[i]);
	}
	
	solve(l,mid);
	solve(mid+1,r);
}
void Init(int m, int A[]) {
  // Secret(0, 1000000000);
  n = m;
  for(int i = n; i>0; i--) {
  	a[i] = A[i-1];
  }
  solve(1,n);
}
 
int Query(int L, int R) { //cout<<"++";cout<<"++";
	L++; R++;
	if(L == R) return a[L];
	int  l = 1, r = n;
	
	  while(true) {
		  	int mid = (l+r)/2;
		  	if(l<=mid && R==mid) return x[L][mid];
		  	if(L==mid+1 && R>mid) return x[mid+1][R];
		  	if(R<=mid) {
		  		r = mid ;
		  		continue;
			} 
			if(L>mid) {
				l = mid + 1;
				continue;
			}
		
		//	cout<<L<<" "<<mid<<" "<<x[L][mid]<<" "<<a[R]<<endl;
		  	return Secret(x[L][mid],x[mid+1][R]);
			
			
	  }
 
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 4276 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 166 ms 4276 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 152 ms 4364 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 546 ms 8104 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 547 ms 8280 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 573 ms 8132 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 549 ms 8252 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 551 ms 8144 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 541 ms 8236 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 528 ms 8188 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1