Submission #923503

#	Time	Username	Problem	Language	Result	Execution time	Memory
923503		Nonoze	Index (COCI21_index)	C++17	60 / 110	2534 ms	63660 KiB

index

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long long ll;


#define int long long
#define sz(x) (int)(x.size())
#define debug(x) cerr << (#x) << ": " << (x) << endl
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()


vector<vector<int>> st;
vector<int> vec;

void query(int root, int left, int right, int qLeft, int qRight)
{
	if (left>qRight || right<qLeft) return;
	if (left>=qLeft && right<=qRight) {
		vec.push_back(root);
		return;
	}
	int mid=(left+right)/2;
	query(root*2, left, mid, qLeft, qRight);
	query(root*2+1, mid+1, right, qLeft, qRight);
}

void build(int root, int left, int right, vector<int>& v)
{
	if (left==right) {
		st[root].push_back(v[left]);
		return;
	}

	int mid=(left+right)/2;
	build(root*2, left, mid, v);
	build(root*2+1, mid+1, right, v);
	st[root]=st[root*2];
	st[root].insert(st[root].end(), all(st[root*2+1]));
	sort(all(st[root]));
	return;
}

int n, q;
vector<int> a;

void solve() {
	cin >> n >> q;
	a.clear(), a.resize(n);
	for (auto &u: a) cin >> u;
	st.resize(4*n);
	build(1, 0, n-1, a);
	while (q--) {
		int ll, rr; cin >> ll >> rr;
		ll--, rr--;
		int l=0, r=rr-ll+1;
		int ans=0;
		vec.clear();
		query(1, 0, n-1, ll, rr);
		while (l<=r) {
			int mid=(l+r)/2;
			int sum=0;
			for (auto &u: vec) {
				sum+=st[u].end()-lower_bound(all(st[u]), mid);
			}
			if (sum>=mid) {
				ans=mid;
				l=mid+1;
			} else {
				r=mid-1;
			}
		}
		cout << ans << endl;
	}
	return;
}


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;// cin >> tt;
	while(tt--) solve();
	return 0;
}

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