oj.uz

Submission #34630

# Submission time Handle Problem Language Result Execution time Memory
34630 2017-11-14T14:45:29 Z cheater2k Secret (JOI14_secret) C++14
100 / 100
 629 ms 13980 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
const int N = 1010;
int n, a[N];
int le[N][N], ri[N][N];
vector <int> Pos;

void Solve(int l, int r) {
	if (l >= r) return;
	int m = (l + r) >> 1; Pos.push_back(m);
	Solve(l, m); Solve(m + 1, r);
	le[m][m] = a[m]; for (int i = m-1; i >= l; i--) le[m][i] = Secret(a[i], le[m][i+1]);
	ri[m+1][m+1] = a[m+1]; for (int i = m+2; i <= r; i++) ri[m+1][i] = Secret(ri[m+1][i-1], a[i]); 
}

void Init(int N, int A[]) {
	n = N; for (int i = 0; i < n; i++) a[i+1] = A[i];	
	Solve(1, n);
}

int M;

int Query(int L, int R) {
	L++; R++;
	if (L == R) return a[R];
	for (int i = 0; i < (int)Pos.size(); i++) if (Pos[i] >= L && Pos[i] <= R) { M = Pos[i]; break; }
	if (M == R) return le[M][L];
	else return Secret(le[M][L], ri[M+1][R]);
}

/*
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
	Init(9, A);
	int q; cin >> q;
	while(q--) {
		int l, r; cin >> l >> r;
		cout << Query(l, r) << endl;
	}
}
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 13980 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 179 ms 13980 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 183 ms 13980 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 619 ms 13980 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 623 ms 13980 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 629 ms 13980 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 626 ms 13980 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 623 ms 13980 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 616 ms 13980 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 626 ms 13980 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1