oj.uz

Submission #343922

# Submission time Handle Problem Language Result Execution time Memory
343922 2021-01-04T18:23:49 Z flappybird medians (balkan11_medians) C++14
90 / 100
 191 ms 22764 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAX 202020
int l[MAX], r[MAX];
int tree[MAX];
int arr[MAX];
int s;
vector<int>ans;
set<int>S;
void init(int x = 1) {
	if (x >= s) {
		l[x] = r[x] = x - s + 1;
		return;
	}
	init(x * 2);
	init(x * 2 + 1);
	l[x] = l[x * 2];
	r[x] = r[x * 2 + 1];
}
void update(int loc) {
	ans.push_back(loc);
	arr[loc] = 1;
	S.erase(loc);
	loc += s - 1;
	while (loc > 0) {
		tree[loc]++;
		loc /= 2;
	}
}
int sumquery(int low, int high, int loc = 1) {
	if (l[loc] == low && r[loc] == high) return tree[loc];
	else if (r[loc * 2] >= high) return sumquery(low, high, loc * 2);
	else if (l[loc * 2 + 1] <= low) return sumquery(low, high, loc * 2 + 1);
	else return sumquery(low, r[loc * 2], loc * 2) + sumquery(l[loc * 2 + 1], high, loc * 2 + 1);
}
int minn() {
	return *S.begin();
}
int maxn() {
	set<int>::iterator it;
	it = S.end();
	it--;
	return *it;
}
int main(void) {
	int N;
	cin >> N;
	s = 1 << (int)ceil(log2(2 * N - 1));
	int i;
	for (i = 1; i <= 2 * N - 1; i++) S.insert(i);
	init();
	int a;
	cin >> a;
	update(a);
	for (i = 1; i <= N - 1; i++) {
		cin >> a;
		if (arr[a] == 0) update(a);
		while (sumquery(1, a) < (i + 1)) update(minn());
		while (sumquery(a, 2 * N - 1) < (i + 1)) update(maxn());
	}
	for (auto i : ans) cout << i << endl;
}

Subtask #1
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 6 ms 492 KB Output is correct

Subtask #2
25.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 620 KB Output is correct
2 Correct 23 ms 1004 KB Output is correct
3 Correct 45 ms 1644 KB Output is correct
4 Correct 93 ms 2944 KB Output is correct
5 Correct 191 ms 5500 KB Output is correct
6 Runtime error 35 ms 16000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 53 ms 22764 KB Execution killed with signal 11 (could be triggered by violating memory limits)