oj.uz

Submission #56555

# Submission time Handle Problem Language Result Execution time Memory
56555 2018-07-11T16:52:11 Z Bruteforceman Secret (JOI14_secret) C++11
100 / 100
 746 ms 5412 KB 
#include "secret.h"
#include "bits/stdc++.h"
using namespace std;
map <int, int> v[1100 * 4];
int a[1100];
int n;

void solve(int c, int b, int e) {
	if(b == e) {
		v[c][b] = a[b];
		return ;
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	solve(l, b, m);
	solve(r, m+1, e);
	if(c == 1) {
		return ;
 	}
	if(c & 1) {
		v[c][b] = a[b];
		for(int i = b + 1; i <= e; i++) {
			v[c][i] = Secret(v[c][i - 1], a[i]);
		}
	} else {
		v[c][e] = a[e];
		for(int i = e - 1; i >= b; i--) {
			v[c][i] = Secret(a[i], v[c][i + 1]);
		}
	}
}

int answer(int x, int y, int c, int b, int e) {
	if(b == e) {
		return a[b];
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(y <= m) {
		return answer(x, y, l, b, m);
	} else if (m < x) {
		return answer(x, y, r, m+1, e);
	} else {
		return Secret(v[l][x], v[r][y]); 
	}
}
void Init(int N, int A[]) {
	for(int i = 0; i < N; i++) {
		a[i] = A[i];
	}
	solve(1, 0, N-1);
	n = N;
}
int Query(int L, int R) {
  return answer(L, R, 1, 0, n-1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 2812 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 193 ms 2812 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 202 ms 2844 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 711 ms 5188 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 659 ms 5188 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 746 ms 5332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 656 ms 5332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 696 ms 5412 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 661 ms 5412 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 612 ms 5412 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1