oj.uz

Submission #365169

# Submission time Handle Problem Language Result Execution time Memory
365169 2021-02-11T04:27:36 Z Bill_00 Secret (JOI14_secret) C++14
100 / 100
 535 ms 8324 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
int a[1001],n;
int ans[1001][1001];
void build(int l,int r){
	if(l>r){
		return;
	}
	if(l==r){
		ans[l][r]=a[l];
		return;
	}
	int m=(l+r)>>1;
	int k=a[m];
	ans[m][m]=a[m];
	for(int i=m-1;i>=l;i--){
		k=Secret(a[i],k);
		ans[i][m]=k;
	}
	k=a[m+1];
	ans[m+1][m+1]=a[m+1];
	for(int i=m+2;i<=r;i++){
		k=Secret(k,a[i]);
		ans[m+1][i]=k;
	}
	build(l,m-1);
	build(m+2,r);
}
int query(int l,int r,int L,int R){
	int m=(l+r)>>1;
	if(L<=m && m<=R){
		if(m==R){
			return ans[L][m];
		}
		else return Secret(ans[L][m],(m+1==R?a[R]:ans[m+1][R]));
	}
	if(L<=(m+1) && (m+1)<=R){
		if(m+1==L){
			return ans[m+1][R];
		}
		else return Secret((m==L?a[L]:ans[L][m]),ans[m+1][R]);
	}
	if(m>R){
		return query(l,m-1,L,R);
	}
	else return query(m+2,r,L,R);
}
void Init(int N, int A[]){
	n=N;
	for(int i=0;i<n;i++) a[i]=A[i];
	build(0,n-1);
}

int Query(int L, int R) {
	if(L==R) return a[L];
	return query(0,n-1,L,R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 4460 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 146 ms 4460 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 145 ms 4460 KB Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1
4 Correct 506 ms 8300 KB Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1
5 Correct 509 ms 8300 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
6 Correct 503 ms 8172 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
7 Correct 508 ms 8300 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 535 ms 8248 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 513 ms 8216 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 521 ms 8324 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1