提出 #328842

---

ソースコード 拡げる

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <numeric>
#define FOR(x, to) for (int x = 0; x < to; x++)

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int Q;

int n;
int dat[1 << 21];

void init() {
	n = 1;
	while (n <= 200000) {
		n *= 2;
	}
}

//[a, b)
//node k
//[l, r)
//query(a, b, 0, 0, r)
int query(int a, int b, int k, int l, int r) {
	if (r <= a || b <= l) return 0;
	if (a <= l && r <= b) return dat[k];
	else {
		int m = (l + r) / 2;
		return query(a, b, 2 * k + 1, l, m) + query(a, b, 2 * k + 2, m, r);
	}
}

void update(int k, int a) {
	k += n - 1;
	dat[k] = a;
	while (k > 0) {
		k = (k - 1) / 2;
		dat[k] = dat[2 * k + 1] + dat[2 * k + 2];
	}
}

int bs(int v) {
	int mn = 0;
	int mx = n;
	while (mx - mn > 1) {
		int m = (mn + mx) / 2;
		int q = query(0, m + 1, 0, 0, n);
		if (q < v) {
			mn = m;
		} else {
			mx = m;
		}
	}
	return mx;
}

int main() {
	init();
	cin >> Q;
	FOR(i, Q) {
		int t, x;
		cin >> t >> x;
		if (t == 1) {
			update(x, 1);
		} else {
			int p = bs(x);
			cout << p << endl;
			update(p, 0);
		}
	}
	return 0;
}

提出情報

ジャッジ結果