oj.uz

Submission #930275

# Submission time Handle Problem Language Result Execution time Memory
930275 2024-02-19T08:56:27 Z noyancanturk Secret (JOI14_secret) C++17
0 / 100
 378 ms 4480 KB 
#include "secret.h"
#include <cassert>
const int lim=1100;

int n,*a;
int left[12][lim],right[12][lim];

void dnc(int l,int r,int dep=0){
	if(l==r){
		return;
	}
	int mid=(l+r)>>1;
	assert(left[dep][mid]==0);
	left[dep][mid]=a[mid];
	for(int i=mid-1;l<=i;i--){
		assert(left[dep][i]==0);
		left[dep][i]=Secret(a[i],left[dep][i+1]);
	}
	assert(mid+1<=r);
	assert(right[dep][mid+1]==0);
	right[dep][mid+1]=a[mid+1];
	for(int i=mid+2;i<=r;i++){
		assert(right[dep][i]==0);
		right[dep][i]=Secret(right[dep][i-1],a[i]);
	}
	dnc(l,mid,dep+1),dnc(mid+1,r,dep+1);
}

void Init(int N, int A[]) {
	n=N;
	a=A;
    dnc(0,n-1);
}

int Query(int L, int R) {
	if(L==R){
		return a[L];
	}
	int l=0,r=n-1,dep=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(L<=mid&&mid<R){
			return Secret(left[dep][L],right[dep][R]);
		}else if(mid<L){
			l=mid+1;
		}else{
			r=mid-1;
		}
		dep++;
	}
	return -1;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 3668 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 101 ms 3604 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Incorrect 96 ms 3668 KB Wrong Answer: Query(128, 153) - expected : 959658850, actual : 473307172.
4 Incorrect 353 ms 4444 KB Wrong Answer: Query(172, 187) - expected : 590352579, actual : 590348483.
5 Incorrect 356 ms 4440 KB Wrong Answer: Query(703, 706) - expected : 857111674, actual : 536870912.
6 Incorrect 361 ms 4436 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 950174288.
7 Correct 370 ms 4352 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 360 ms 4444 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 377 ms 4440 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 378 ms 4480 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1