oj.uz

Submission #1046889

# Submission time Handle Problem Language Result Execution time Memory
1046889 2024-08-07T05:53:51 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 955 ms 133480 KB 
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
	#include "debug.h"
#else 
	#define debug(...) void(23)
#endif

struct node {
	i64 val;
	node *l, *r;
	node() : val(0), l(nullptr), r(nullptr) {}
	node(i64 x) : val(x), l(nullptr), r(nullptr) {}
	node(node *L, node *R) : val(L->val + R->val), l(L), r(R) {}
	node(node *x) : val(x->val), l(x->l), r(x->r) {}
};

constexpr int maxN = int(2E5) + 5;

int A[maxN];
node* roots[maxN];
node* build(int l, int r) {
	if(l == r) {
		return new node();
	}
	int mid = (l + r) >> 1;
	return new node(build(l, mid), build(mid + 1, r));
}

node* modify(node *v, int l, int r, int p) {
	if(l == r) {
		return new node(v->val + 1);
	}
	int mid = (l + r) >> 1;
	if(p <= mid) {
		return new node(modify(v->l, l, mid, p), v->r);
	}
	return new node(v->l, modify(v->r, mid + 1, r, p));
}

i64 query(node *vl, node *vr, int l, int r, int ql, int qr) {
	if(ql <= l && r <= qr) {
		return vr->val - vl->val;
	} else if(r < ql || qr < l) {
		return 0;
	}
	int mid = (l + r) >> 1;
	return query(vl->l, vr->l, l, mid, ql, qr)
		+ query(vl->r, vr->r, mid + 1, r, ql, qr);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int N, Q;
	std::cin >> N >> Q;

	roots[0] = build(1, maxN);
	for(int i = 1; i <= N; ++i) {
		std::cin >> A[i];
		roots[i] = modify(roots[i - 1], 1, maxN, A[i]);
	}

	while(Q--) {
		int L, R;
		std::cin >> L >> R;
		int lo = 0, hi = R - L + 1;
		while(lo < hi) {
			int mid = (lo + hi + 1) >> 1;
			debug(query(roots[L - 1], roots[R], 1, maxN, mid, maxN));
			if(query(roots[L - 1], roots[R], 1, maxN, mid, maxN) >= mid) {
				lo = mid;
			} else {
				hi = mid - 1;
			}
		}
		std::cout << lo << '\n';
	}

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15452 KB Output is correct
2 Correct 10 ms 15452 KB Output is correct
3 Correct 10 ms 15452 KB Output is correct
4 Correct 10 ms 15452 KB Output is correct
5 Correct 11 ms 15452 KB Output is correct
6 Correct 10 ms 15608 KB Output is correct
7 Correct 10 ms 15520 KB Output is correct
8 Correct 10 ms 15448 KB Output is correct
9 Correct 11 ms 15452 KB Output is correct
10 Correct 10 ms 15476 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15452 KB Output is correct
2 Correct 10 ms 15452 KB Output is correct
3 Correct 10 ms 15452 KB Output is correct
4 Correct 10 ms 15452 KB Output is correct
5 Correct 11 ms 15452 KB Output is correct
6 Correct 10 ms 15608 KB Output is correct
7 Correct 10 ms 15520 KB Output is correct
8 Correct 10 ms 15448 KB Output is correct
9 Correct 11 ms 15452 KB Output is correct
10 Correct 10 ms 15476 KB Output is correct
11 Correct 176 ms 44636 KB Output is correct
12 Correct 160 ms 44628 KB Output is correct
13 Correct 159 ms 44628 KB Output is correct
14 Correct 157 ms 44628 KB Output is correct
15 Correct 157 ms 44624 KB Output is correct
16 Correct 153 ms 44628 KB Output is correct
17 Correct 160 ms 44624 KB Output is correct
18 Correct 162 ms 44628 KB Output is correct
19 Correct 174 ms 44624 KB Output is correct
20 Correct 176 ms 44712 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15452 KB Output is correct
2 Correct 10 ms 15452 KB Output is correct
3 Correct 10 ms 15452 KB Output is correct
4 Correct 10 ms 15452 KB Output is correct
5 Correct 11 ms 15452 KB Output is correct
6 Correct 10 ms 15608 KB Output is correct
7 Correct 10 ms 15520 KB Output is correct
8 Correct 10 ms 15448 KB Output is correct
9 Correct 11 ms 15452 KB Output is correct
10 Correct 10 ms 15476 KB Output is correct
11 Correct 176 ms 44636 KB Output is correct
12 Correct 160 ms 44628 KB Output is correct
13 Correct 159 ms 44628 KB Output is correct
14 Correct 157 ms 44628 KB Output is correct
15 Correct 157 ms 44624 KB Output is correct
16 Correct 153 ms 44628 KB Output is correct
17 Correct 160 ms 44624 KB Output is correct
18 Correct 162 ms 44628 KB Output is correct
19 Correct 174 ms 44624 KB Output is correct
20 Correct 176 ms 44712 KB Output is correct
21 Correct 933 ms 133480 KB Output is correct
22 Correct 955 ms 133456 KB Output is correct
23 Correct 935 ms 133464 KB Output is correct
24 Correct 918 ms 133456 KB Output is correct
25 Correct 916 ms 133456 KB Output is correct
26 Correct 923 ms 133404 KB Output is correct
27 Correct 908 ms 133460 KB Output is correct
28 Correct 897 ms 133316 KB Output is correct
29 Correct 921 ms 133476 KB Output is correct
30 Correct 947 ms 133456 KB Output is correct