oj.uz

Submission #29099

# Submission time Handle Problem Language Result Execution time Memory
29099 2017-07-18T08:47:46 Z cdemirer Secret (JOI14_secret) C++14
30 / 100
 703 ms 6036 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int _N;

typedef struct NodeTag {
	int llim, rlim;
	int value;
} Node;
const int segsz = 2048;
Node seg[segsz];
int offset = segsz / 2;
#define left(x) ((x)*2)
#define right(x) ((x)*2+1)
#define parent(x) ((x)/2)

int combineval(int a, int b) {
	if (a == -1) return -1;
	if (b == -1) return a;
	return Secret(a, b);
}
int combine(int a, int b) {
	return combineval(seg[a].value, seg[b].value);
}

int get(int x, int l, int r) {
	int llim = seg[x].llim;
	int rlim = seg[x].rlim;
	int mid = (llim + rlim) / 2;
	if (l == llim && r == rlim) return seg[x].value;
	else if (l > mid) return get(right(x), l, r);
	else if (r <= mid) return get(left(x), l, r);
	else {
		int a = get(left(x), l, mid);
		int b = get(right(x), mid+1, r);
		return combineval(a, b);
	}
}

void Init(int N, int A[]) {
	_N = N;
	for (int i = offset; i < segsz; i++) {
		seg[i].llim = seg[i].rlim = i-offset;
		seg[i].value = -1;
		if (i-offset < N) seg[i].value = A[i-offset];
	}
	for (int i = offset-1; i > 0; i--) {
		seg[i].llim = seg[left(i)].llim;
		seg[i].rlim = seg[right(i)].rlim;
		seg[i].value = combine(left(i), right(i));
	}
}

int Query(int L, int R) {
	return get(1, L, R);
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 233 ms 6036 KB Output is partially correct - number of calls to Secret by Init = 510, maximum number of calls to Secret by Query = 14
2 Partially correct 216 ms 6036 KB Output is partially correct - number of calls to Secret by Init = 511, maximum number of calls to Secret by Query = 14
3 Partially correct 226 ms 6036 KB Output is partially correct - number of calls to Secret by Init = 512, maximum number of calls to Secret by Query = 14
4 Partially correct 659 ms 6036 KB Output is partially correct - number of calls to Secret by Init = 998, maximum number of calls to Secret by Query = 15
5 Partially correct 686 ms 6036 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 14
6 Partially correct 636 ms 6036 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 4
7 Partially correct 673 ms 6036 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 16
8 Partially correct 679 ms 6036 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 16
9 Partially correct 703 ms 6036 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 15
10 Partially correct 689 ms 6036 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 16