oj.uz

Submission #343935

# Submission time Handle Problem Language Result Execution time Memory
343935 2021-01-04T19:03:25 Z flappybird medians (balkan11_medians) C++14
95 / 100
 300 ms 13400 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAX 302020
int l[MAX], r[MAX];
int tree[MAX];
int arr[MAX];
int s, d;
vector<int>ans;
set<int>S;
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 lg(int x) {
	int cnt = 0;
	while (x) {
		x /= 2;
		cnt++;
	}
	return cnt - 1;
}
int sumquery(int low, int high, int loc = 1) {
	int l, r;
	int ll, rr;
	int res = lg(loc);
	int a = d - res;
	int pw = 1 << a;
	l = (loc - (1 << res))*pw;
	r = l + pw - 1;
	rr = (l + r) / 2;
	ll = rr + 1;
	l++;
	r++;
	ll++;
	rr++;
	if (l == low && r == high) return tree[loc];
	else if (rr >= high) return sumquery(low, high, loc * 2);
	else if (ll <= low) return sumquery(low, high, loc * 2 + 1);
	else return sumquery(low, rr, loc * 2) + sumquery(ll, 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;
	scanf("%d", &N);
	d = (int)ceil(log2(2 * N - 1));
	s = 1 << d;
	int i;
	for (i = 1; i <= 2 * N - 1; i++) S.insert(i);
	int a;
	scanf("%d", &a);
	update(a);
	int r1, r2;
	for (i = 1; i <= N - 1; i++) {
		scanf("%d", &a);
		if (arr[a] == 0) update(a);
		r1 = sumquery(1, a);
		r2 = sumquery(a, 2 * N - 1);
		while (sumquery(1, a) < (i + 1)) {
			update(minn());
			r1++;
		}
		while (sumquery(a, 2 * N - 1) < (i + 1)) {
			update(maxn());
			r2++;
		}
	}
	for (auto i : ans) printf("%d\n", i);
}

Compilation message

medians.cpp: In function 'int main()':
medians.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
medians.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d", &a);
      |  ~~~~~^~~~~~~~~~
medians.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |   scanf("%d", &a);
      |   ~~~~~^~~~~~~~~~

Subtask #1
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 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 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 3 ms 492 KB Output is correct

Subtask #2
30.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 748 KB Output is correct
2 Correct 14 ms 876 KB Output is correct
3 Correct 25 ms 1388 KB Output is correct
4 Correct 54 ms 2412 KB Output is correct
5 Correct 122 ms 4460 KB Output is correct
6 Correct 267 ms 8768 KB Output is correct
7 Execution timed out 479 ms 13400 KB Time limit exceeded