Submission #747040

#	Time	Username	Problem	Language	Result	Execution time	Memory
747040		Szil	Index (COCI21_index)	C++17	60 / 110	2555 ms	136324 KiB

index

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

const int MAXN = 200001;

struct Node {
	Node *l, *r;
	int sum = 0;

	Node(Node *left, Node *right) : l(left), r(right) {
		if (l) sum += l->sum;
		if (r) sum += r->sum;
	}

	Node(int s) : sum(s) {}
};

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

Node *upd(Node *v, int tl, int tr, int pos) {
	if (tl == tr) {
		return new Node(v->sum+1);
	} else {
		int tm = (tl + tr) / 2;
		if (pos <= tm) {
			return new Node(upd(v->l, tl, tm, pos), v->r);
		} else {
			return new Node(v->l, upd(v->r, tm+1, tr, pos));
		}
	}
}

int qry(Node *v, int tl, int tr, int l, int r) {
	if (l > r) return 0;
	if (l == tl && r == tr) {
		return v->sum;
	} else {
		int tm = (tl + tr) / 2;
		return qry(v->l, tl, tm, l, min(tm, r)) + qry(v->r, tm+1, tr, max(tm+1, l), r);
	}
}

const int MAXV = 200001;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	vector<Node *> roots = {build(1, MAXV)};
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		roots.push_back(upd(roots.back(), 1, MAXV, x));
	}
	while (q--) {
		int l, r; cin >> l >> r;
		int lo = 1, hi = r-l+1;
		while (lo < hi) {
			int mid = (lo + hi + 1) / 2;
			int cnt = qry(roots[r], 1, MAXV, mid, MAXV) - qry(roots[l-1], 1, MAXV, mid, MAXV);
			if (cnt >= mid) {
				lo = mid;
			} else {
				hi = mid - 1;
			}
		}
		cout << lo << "\n";
	}
}

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