Submission #923334

#	Time	Username	Problem	Language	Result	Execution time	Memory
923334		Nonoze	Index (COCI21_index)	C++17	60 / 110	2526 ms	63324 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()


struct node
{
	node* left, *right;
	vector<int> vec;
	void update() {
		vec=left->vec;
		vec.insert(vec.end(), all(right->vec));
		sort(all(vec));
	}
};

int query(node* root, int left, int right, int qLeft, int qRight, int val)
{
	if (left>qRight || right<qLeft) return 0;
	if (left>=qLeft && right<=qRight) {
		return root->vec.end()-lower_bound(all(root->vec), val);
	}
	int mid=(left+right)/2;
	int s1=query(root->left, left, mid, qLeft, qRight, val);
	int s2=query(root->right, mid+1, right, qLeft, qRight, val);
	return s1+s2;
}

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

	root->left=new node{NULL, NULL};
	root->right=new node{NULL, NULL};

	int mid=(left+right)/2;
	build(root->left, left, mid, v);
	build(root->right, mid+1, right, v);
	root->update();
	return;
}


int n, q;
vector<int> a;

void solve() {
	cin >> n >> q;
	a.clear(), a.resize(n);
	for (auto &u: a) cin >> u;
	node *root=new node{NULL, NULL};
	build(root, 0, n-1, a);
	while (q--) {
		int ll, rr; cin >> ll >> rr;
		ll--, rr--;
		int l=0, r=rr-ll+1;
		int ans=0;
		while (l<=r) {
			int mid=(l+r)/2;
			if (query(root, 0, n-1, ll, rr, mid)>=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