Submission #996238

#	Time	Username	Problem	Language	Result	Execution time	Memory
996238		dubabuba	Index (COCI21_index)	C++14	110 / 110	664 ms	137080 KiB

index

#include <bits/stdc++.h>
using namespace std;

struct tree {
	int sum;
	tree *lc, *rc;

	tree() : sum(0), lc(nullptr), rc(nullptr) {};
	tree(int x) : sum(x), lc(nullptr), rc(nullptr) {};
	tree(tree *L, tree *R) {
		sum = 0;
		lc = L, rc = R;
		if(lc) sum += lc->sum;
		if(rc) sum += rc->sum;
	}
};

const int mxn = 2e5 + 10;
int sum(tree *sus) { return sus->sum; }
int a[mxn], n, q;
tree *root[mxn];

tree *build(int tl, int tr) {
	if(tl == tr) return new tree(0);
	int tm = (tl + tr) / 2;
	return new tree(build(tl, tm), build(tm + 1, tr));
}

tree *upt(tree *sus, int tl, int tr, int pos, int add) {
	if(tl == tr) return new tree(sum(sus) + add);
	int tm = (tl + tr) / 2;
	if(pos <= tm) {
		tree *LC = upt(sus->lc, tl, tm, pos, add);
		return new tree(LC, sus->rc);
	} else {
		tree *RC = upt(sus->rc, tm + 1, tr, pos, add);
		return new tree(sus->lc, RC);
	}
	return nullptr;
}

int query(tree *L, tree *R, int tl, int tr, int adder) {
	if(tl == tr) return tr;
	int tm = (tl + tr) / 2;
	int cnt = sum(R->rc) - sum(L->rc) + adder;
	// cout << "(" << tl << ") " << tm + 1 << " to " << tr << " = " << cnt << endl;
	if(tm + 1 > cnt) return query(L->lc, R->lc, tl, tm, cnt);
	return query(L->rc, R->rc, tm + 1, tr, adder);
}

void print(tree *sus, int tl, int tr) {
	// cout << tl << " -> " << tr << ": " << sum(sus) << endl;
	if(tl == tr) return;
	int tm = (tl + tr) / 2;
	print(sus->lc, tl, tm);
	print(sus->rc, tm + 1, tr);
}

int main() {
	cin >> n >> q;

	root[0] = build(1, n);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		root[i] = upt(root[i - 1], 1, n, a[i], 1);
		// print(root[i], 1, n);
		// cout << endl;
	}

	while(q--) {
		int l, r;
		cin >> l >> r;
		// cout << "query: " << l << ' ' << r << endl;
		cout << query(root[l - 1], root[r], 1, n, 0) << endl;
	}
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50