제출 #1153857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153857		siewjh	Index (COCI21_index)	C++20	60 / 110	2514 ms	206220 KiB

index

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
struct node{
	int s, e, m, val;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1, val = 0;
		if (s != e){
			l = new node(s, m); r = new node(m + 1, e);
		}
	}
	node (node *x){
		s = x->s, e = x->e, m = x->m, val = x->val, l = x->l, r = x->r;
	}
	void update(int x, int v){
		if (s == e){
			val += v; return;
		}
		if (x <= m){
			l = new node(l); l->update(x, v);
		}
		else{
			r = new node(r); r->update(x, v);
		}
		val = l->val + r->val;
	}
	int query(int x, int y){
		if (x == s && y == e) return val;
		else if (y <= m) return l->query(x, y);
		else if (x > m) return r->query(x, y);
		else return l->query(x, m) + r->query(m + 1, y);
	}
};
node *root[MAXN];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int nums, queries; cin >> nums >> queries;
	vector<vector<int>> vec(nums + 1);
	for (int i = 1; i <= nums; i++){
		int x; cin >> x; x = min(x, nums);
		vec[x].push_back(i);
	}
	root[0] = new node(1, nums);
	for (int x = 1; x <= nums; x++){
		root[x] = new node(root[x - 1]);
		for (int i : vec[x]) root[x]->update(i, 1);
	}
	while (queries--){
		int l, r, sz; cin >> l >> r; sz = r - l + 1;
		int lo = 1, hi = sz, ans;
		while (lo <= hi){
			int m = (lo + hi) >> 1;
			if (sz - root[m - 1]->query(l, r) >= m){
				ans = m; lo = m + 1;
			}
			else hi = m - 1;
		}
		cout << ans << '\n';
	}
}

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