oj.uz

Submission #239194

# Submission time Handle Problem Language Result Execution time Memory
239194 2020-06-14T18:44:31 Z rqi Secret (JOI14_secret) C++14
100 / 100
 526 ms 4472 KB 
#include "secret.h"
#include <bits/stdc++.h>
int A[1005];
int val[1005][10];
int N;
void build(int L, int R, int lvl = 0){
	if(L > R) return;
	if(L == R){
		val[L][lvl] = A[L];
		return;
	}
	int M = (L+R)/2;
	val[M][lvl] = A[M];
	for(int i = M-1; i >= L; i--){
		val[i][lvl] = Secret(A[i], val[i+1][lvl]);
	}
	val[M+1][lvl] = A[M+1];
	for(int i = M+2; i <= R; i++){
		val[i][lvl] = Secret(val[i-1][lvl], A[i]);
	}
	build(L, M-1, lvl+1);
	build(M+2, R, lvl+1);
}

int query(int l, int r, int L = 0, int R = N-1, int lvl = 0){
	int M = (L+R)/2;
	if(r <= M-1){
		return query(l, r, L, M-1, lvl+1);
	}
	if(l >= M+2){
		return query(l, r, M+2, R, lvl+1);
	}
	
	if(l >= M+1){
		return val[r][lvl];
	}
	if(r <= M){
		return val[l][lvl];
	}

	return Secret(val[l][lvl], val[r][lvl]);
}




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) {
	return query(L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 2528 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 145 ms 2424 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 146 ms 2424 KB Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1
4 Correct 511 ms 4440 KB Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1
5 Correct 504 ms 4388 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
6 Correct 517 ms 4360 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
7 Correct 507 ms 4472 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 506 ms 4344 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 516 ms 4472 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 526 ms 4396 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1