oj.uz

Submission #923334

# Submission time Handle Problem Language Result Execution time Memory
923334 2024-02-07T06:37:49 Z Nonoze Index (COCI21_index) C++17
60 / 110
 2500 ms 63324 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;
		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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 856 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 4 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 4 ms 604 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 856 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 4 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 650 ms 15388 KB Output is correct
12 Correct 647 ms 15332 KB Output is correct
13 Correct 645 ms 15504 KB Output is correct
14 Correct 657 ms 15248 KB Output is correct
15 Correct 650 ms 15428 KB Output is correct
16 Correct 650 ms 15432 KB Output is correct
17 Correct 647 ms 15696 KB Output is correct
18 Correct 645 ms 15416 KB Output is correct
19 Correct 660 ms 15248 KB Output is correct
20 Correct 645 ms 15316 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 856 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 4 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 650 ms 15388 KB Output is correct
12 Correct 647 ms 15332 KB Output is correct
13 Correct 645 ms 15504 KB Output is correct
14 Correct 657 ms 15248 KB Output is correct
15 Correct 650 ms 15428 KB Output is correct
16 Correct 650 ms 15432 KB Output is correct
17 Correct 647 ms 15696 KB Output is correct
18 Correct 645 ms 15416 KB Output is correct
19 Correct 660 ms 15248 KB Output is correct
20 Correct 645 ms 15316 KB Output is correct
21 Execution timed out 2526 ms 63324 KB Time limit exceeded
22 Halted 0 ms 0 KB -