oj.uz

Submission #284497

# Submission time Handle Problem Language Result Execution time Memory
284497 2020-08-27T13:56:24 Z NaimSS Secret (JOI14_secret) C++14
100 / 100
 535 ms 4600 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;


const int N = 1010;
int ans[N][11];
int ar[N];
void build(int l,int r,int level){
	if(l == r){
		ans[l][level] = ar[l];
		return;
	}
	int mid = (l+r)/2;
	ans[mid][level] = ar[mid];
	ans[mid+1][level] = ar[mid+1];
	int last = ar[mid];
	for(int i=mid-1;i>=l;i--){
		ans[i][level] = Secret(ar[i],last);
		last = ans[i][level];
	}
	last = ar[mid+1];
	for(int i=mid+2;i<=r;i++){
		ans[i][level] = Secret(last,ar[i]);
		
		last = ans[i][level];
	}
	build(l,mid,level+1);
	build(mid+1,r,level+1);
}
int n;
void Init(int N, int A[]) {
  n = N;
  for(int i=1;i<=N;i++)ar[i] = A[i-1];
  build(1,N,0);
}

int go(int l,int r,int level,int a,int b){
	if(l == r){
		return ans[l][level];
	}

	int mid = (l + r)/2;
	if(a<=mid and b>mid){
	return Secret(ans[a][level],ans[b][level]);
	}
	if(a<=mid)return go(l,mid,level + 1,a,b);
	return go(mid+1,r,level + 1,a,b);
}

int Query(int L, int R) {
	assert(L>=0 and R<n);
//	cout <<"lets go "<<" "<<L<<" "<<R<<endl;
	return go(1,n,0,L+1,R+1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 2552 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 2680 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 145 ms 2552 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 509 ms 4472 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 522 ms 4444 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 535 ms 4560 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 522 ms 4600 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 507 ms 4440 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 526 ms 4396 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 520 ms 4600 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1