oj.uz

Submission #747047

# Submission time Handle Problem Language Result Execution time Memory
747047 2023-05-23T13:16:53 Z Szil Index (COCI21_index) C++14
110 / 110
 1811 ms 136384 KB 
#include <bits/stdc++.h>
using namespace std;

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 = 200005;

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 = MAXV;
		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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13352 KB Output is correct
2 Correct 18 ms 13396 KB Output is correct
3 Correct 21 ms 13444 KB Output is correct
4 Correct 19 ms 13392 KB Output is correct
5 Correct 20 ms 13388 KB Output is correct
6 Correct 24 ms 13396 KB Output is correct
7 Correct 18 ms 13368 KB Output is correct
8 Correct 20 ms 13396 KB Output is correct
9 Correct 19 ms 13428 KB Output is correct
10 Correct 17 ms 13396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13352 KB Output is correct
2 Correct 18 ms 13396 KB Output is correct
3 Correct 21 ms 13444 KB Output is correct
4 Correct 19 ms 13392 KB Output is correct
5 Correct 20 ms 13388 KB Output is correct
6 Correct 24 ms 13396 KB Output is correct
7 Correct 18 ms 13368 KB Output is correct
8 Correct 20 ms 13396 KB Output is correct
9 Correct 19 ms 13428 KB Output is correct
10 Correct 17 ms 13396 KB Output is correct
11 Correct 340 ms 42956 KB Output is correct
12 Correct 316 ms 42908 KB Output is correct
13 Correct 346 ms 42960 KB Output is correct
14 Correct 314 ms 42824 KB Output is correct
15 Correct 313 ms 42884 KB Output is correct
16 Correct 327 ms 42832 KB Output is correct
17 Correct 322 ms 42912 KB Output is correct
18 Correct 340 ms 42984 KB Output is correct
19 Correct 315 ms 42840 KB Output is correct
20 Correct 390 ms 42864 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13352 KB Output is correct
2 Correct 18 ms 13396 KB Output is correct
3 Correct 21 ms 13444 KB Output is correct
4 Correct 19 ms 13392 KB Output is correct
5 Correct 20 ms 13388 KB Output is correct
6 Correct 24 ms 13396 KB Output is correct
7 Correct 18 ms 13368 KB Output is correct
8 Correct 20 ms 13396 KB Output is correct
9 Correct 19 ms 13428 KB Output is correct
10 Correct 17 ms 13396 KB Output is correct
11 Correct 340 ms 42956 KB Output is correct
12 Correct 316 ms 42908 KB Output is correct
13 Correct 346 ms 42960 KB Output is correct
14 Correct 314 ms 42824 KB Output is correct
15 Correct 313 ms 42884 KB Output is correct
16 Correct 327 ms 42832 KB Output is correct
17 Correct 322 ms 42912 KB Output is correct
18 Correct 340 ms 42984 KB Output is correct
19 Correct 315 ms 42840 KB Output is correct
20 Correct 390 ms 42864 KB Output is correct
21 Correct 1811 ms 132800 KB Output is correct
22 Correct 1737 ms 132808 KB Output is correct
23 Correct 1801 ms 136324 KB Output is correct
24 Correct 1799 ms 136360 KB Output is correct
25 Correct 1734 ms 136256 KB Output is correct
26 Correct 1542 ms 136272 KB Output is correct
27 Correct 1610 ms 136340 KB Output is correct
28 Correct 1563 ms 136384 KB Output is correct
29 Correct 1741 ms 136384 KB Output is correct
30 Correct 1620 ms 136368 KB Output is correct