Submission #1046889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046889		vjudge1	Index (COCI21_index)	C++17	110 / 110	955 ms	133480 KiB

index

#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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50