oj.uz

Submission #171047

# Submission time Handle Problem Language Result Execution time Memory
171047 2019-12-27T08:11:50 Z ZwariowanyMarcin Secret (JOI14_secret) C++14
100 / 100
 657 ms 4496 KB 
#include "secret.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)
 
using namespace std;
 
int n;
int a[1024];
int val[1024][11];
 
void dc(int l, int r, int lvl) {
	if(l >= r) return;
	int m = (l + r) / 2;
	val[m][lvl] = a[m];
	for(int j = m - 1; l <= j; --j)
		val[j][lvl] = Secret(a[j], val[j + 1][lvl]);
	val[m + 1][lvl] = a[m + 1];
	for(int j = m + 2; j <= r; ++j)
		val[j][lvl] = Secret(val[j - 1][lvl], a[j]);
	dc(l, m, lvl + 1);
	dc(m + 1, r, lvl + 1);
}
 
void Init(int N, int A[]) {
	n = N;
	for(int i = 0; i < n; ++i)
		a[i] = A[i];
	dc(0, n - 1, 0);
}
 
int solve(int x, int y, int l, int r, int lvl = 0) {
	int m = (l + r) / 2;
	if(x <= m && m + 1 <= y) 
		return Secret(val[x][lvl], val[y][lvl]);
	if(y <= m)
		return solve(x, y, l, m, lvl + 1);
	return solve(x, y, m + 1, r, lvl + 1);
}
 
int Query(int l, int r) {
	if(l == r) return a[l];
	return solve(l, r, 0, n - 1);
}
 
/*int main() {
	int A[] = {1, 4, 7, 2, 5, 8, 3, 6};
	Init(8, A);
	cout << Query(0, 3) << endl;
	cout << Query(1, 7) << endl;
	cout << Query(5, 5) << endl;
	cout << Query(2, 4) << endl;
	
	
	
	return 0;
}
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 2460 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 170 ms 2464 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 171 ms 2464 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 595 ms 4396 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 595 ms 4416 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 606 ms 4496 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 657 ms 4460 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 596 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 596 ms 4428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 597 ms 4376 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1