oj.uz

Submission #923333

# Submission time Handle Problem Language Result Execution time Memory
923333 2024-02-07T06:36:49 Z Nonoze Index (COCI21_index) C++17
0 / 110
 4 ms 604 KB 
#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;
		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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -