oj.uz

Submission #25245

# Submission time Handle Problem Language Result Execution time Memory
25245 2017-06-21T04:18:46 Z zigui Secret (JOI14_secret) C++14
100 / 100
 649 ms 5348 KB 
#include "secret.h"
#include<vector>

using namespace std;

const int MX = 1005;

vector<int> L[MX], R[MX];
int B[MX], N;

void get_LR(int s, int e, int A[]){
	if( s == e ) return;
	int m = (s+e) / 2;
	L[m].push_back(A[m]);
	for(int i = m-1; i >= s; i--){
		L[m].push_back(Secret(A[i], L[m].back()));
	}
	R[m].push_back(A[m+1]);
	for(int i = m+2; i <= e; i++){
		R[m].push_back(Secret(R[m].back(), A[i]));
	}
	get_LR(s, m, A);
	get_LR(m+1, e, A);
}

void Init(int N, int A[]) {
	::N = N;
	get_LR(0, N-1, A);
	for(int i = 0; i < N; i++) B[i] = A[i];
}

int get_answer(int s, int e, int l, int r){
	int m = (s+e) / 2;
	if( l <= m && m+1 <= r ){
		return Secret(L[m][m-l], R[m][r-m-1]);
	}
	else if( m < l ) return get_answer(m+1, e, l, r);
	else return get_answer(s, m, l, r);
}

int Query(int L, int R) {
	if( L == R ) return B[L];
	return get_answer(0, N-1, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 5216 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 186 ms 5216 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 176 ms 5216 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 649 ms 5348 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 619 ms 5348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 626 ms 5348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 636 ms 5348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 636 ms 5348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 636 ms 5348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 636 ms 5348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1