Submission #1153877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153877		siewjh	Index (COCI21_index)	C++20	110 / 110	319 ms	30308 KiB

index

#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> i3;
const int MAXN = 200005;
int fw[MAXN], ans[MAXN];
vector<int> vec[MAXN];
int nums, queries; 
void update(int x, int v){
	while (x <= nums){
		fw[x] += v;
		x += (x & (-x));
	}
}
int query(int x){
	int ans = 0;
	while (x){
		ans += fw[x];
		x -= (x & (-x));
	}
	return ans;
}
void dnc(int lo, int hi, int pm, vector<i3> &qv){
	if (lo > hi) return;
	int m = (lo + hi) >> 1;
	for (int x = pm; x < m; x++){
		for (int i : vec[x])
			update(i, 1);
	}
	vector<i3> lqv, rqv;
	for (auto &[l, r, id] : qv){
		if (r - l + 1 - (query(r) - query(l - 1)) >= m){
			ans[id] = m;
			rqv.push_back({l, r, id});
		}
		else lqv.push_back({l, r, id});
	}
	dnc(m + 1, hi, m, rqv);
	for (int x = pm; x < m; x++){
		for (int i : vec[x])
			update(i, -1);
	}
	dnc(lo, m - 1, pm, lqv);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> nums >> queries;
	for (int i = 1; i <= nums; i++){
		int x; cin >> x; x = min(x, nums);
		vec[x].push_back(i);
	}
	vector<i3> qv(queries);
	for (int i = 0; i < queries; i++){
		int l, r; cin >> l >> r;
		qv[i] = {l, r, i};
	}
	dnc(1, nums, 1, qv);
	for (int i = 0; i < queries; i++) cout << ans[i] << '\n';
}

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