oj.uz

Submission #923503

# Submission time Handle Problem Language Result Execution time Memory
923503 2024-02-07T10:58:32 Z Nonoze Index (COCI21_index) C++17
60 / 110
 2500 ms 63660 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()


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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 4 ms 600 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 4 ms 600 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 4 ms 600 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 4 ms 600 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 4 ms 600 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 4 ms 600 KB Output is correct
11 Correct 557 ms 14628 KB Output is correct
12 Correct 573 ms 15544 KB Output is correct
13 Correct 567 ms 15520 KB Output is correct
14 Correct 556 ms 15336 KB Output is correct
15 Correct 555 ms 15244 KB Output is correct
16 Correct 572 ms 15772 KB Output is correct
17 Correct 572 ms 15900 KB Output is correct
18 Correct 562 ms 15244 KB Output is correct
19 Correct 555 ms 15240 KB Output is correct
20 Correct 557 ms 15248 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 4 ms 600 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 4 ms 600 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 4 ms 600 KB Output is correct
11 Correct 557 ms 14628 KB Output is correct
12 Correct 573 ms 15544 KB Output is correct
13 Correct 567 ms 15520 KB Output is correct
14 Correct 556 ms 15336 KB Output is correct
15 Correct 555 ms 15244 KB Output is correct
16 Correct 572 ms 15772 KB Output is correct
17 Correct 572 ms 15900 KB Output is correct
18 Correct 562 ms 15244 KB Output is correct
19 Correct 555 ms 15240 KB Output is correct
20 Correct 557 ms 15248 KB Output is correct
21 Execution timed out 2534 ms 63660 KB Time limit exceeded
22 Halted 0 ms 0 KB -