oj.uz

Submission #968533

# Submission time Handle Problem Language Result Execution time Memory
968533 2024-04-23T14:50:47 Z penguin133 Index (COCI21_index) C++17
110 / 110
 687 ms 47360 KB 
// CPP program for querying in
// wavelet tree Data Structure
#include <bits/stdc++.h>
using namespace std;
#define N 200005
 
// Given Array
int a[N];
 
// wavelet tree class
struct wavelet_tree{
	int lo, hi;
	wavelet_tree *l, *r;
	vector<int>b;
	
	wavelet_tree(int *from, int *to, int x, int y){
		lo = x, hi = y;
		if(lo == hi || from >= to)return;
		int mid = (lo + hi)/2;
		auto f = [mid](int x){
			return x <= mid;
		};
		b.reserve(to-from+1);
		b.push_back(0);
		for(auto it = from;it != to;it++){
			b.push_back(b.back() + f(*it));
		}
		
		auto pivot = stable_partition(from, to, f);
		l = new wavelet_tree(from, pivot, lo, mid);
		r = new wavelet_tree(pivot, to, mid+1, hi);
	}
	
	int kth(int l, int r, int k){
		if(l > r)return 0;
		if(lo == hi)return lo;
		int inleft = b[r] - b[l-1];
		int lb = b[l-1];
		int rb = b[r];
		if(k <= inleft)return this->l->kth(lb+1, rb, k);
		return this->r->kth(l-lb, r-rb, k-inleft);
	}
};
 
// Driver code
int maxi, mini = 1e9;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
    int n, q;cin >> n >> q;
     
    for(int i=1;i<=n;i++)cin >> a[i];
    wavelet_tree hi(a+1, a + 1 + n, 0, 2e5);
    //cout << hi.kth(4, 5, 2) << '\n';
    while(q--){
    	int l,r; cin >> l >> r;
    	int s = 0, e = r-l+1, ans = 0;
    	while(s <= e){
    		int m = (s + e)/2;
    		if(hi.kth(l, r, (r-l+1) - m + 1) >= m)ans = m, s = m + 1;
    		else e = m -1;
		}
		cout << ans << '\n';
	}
	
    // count of elements less than 2 in range [1,3]
    //cout << obj.kOrLess(0, 3, 2) << '\n';
 
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 704 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 122 ms 12012 KB Output is correct
12 Correct 125 ms 11932 KB Output is correct
13 Correct 124 ms 12364 KB Output is correct
14 Correct 127 ms 11904 KB Output is correct
15 Correct 118 ms 12012 KB Output is correct
16 Correct 121 ms 12012 KB Output is correct
17 Correct 115 ms 12012 KB Output is correct
18 Correct 117 ms 11888 KB Output is correct
19 Correct 122 ms 11860 KB Output is correct
20 Correct 123 ms 12052 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 704 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 122 ms 12012 KB Output is correct
12 Correct 125 ms 11932 KB Output is correct
13 Correct 124 ms 12364 KB Output is correct
14 Correct 127 ms 11904 KB Output is correct
15 Correct 118 ms 12012 KB Output is correct
16 Correct 121 ms 12012 KB Output is correct
17 Correct 115 ms 12012 KB Output is correct
18 Correct 117 ms 11888 KB Output is correct
19 Correct 122 ms 11860 KB Output is correct
20 Correct 123 ms 12052 KB Output is correct
21 Correct 687 ms 47052 KB Output is correct
22 Correct 652 ms 47032 KB Output is correct
23 Correct 687 ms 47228 KB Output is correct
24 Correct 674 ms 47256 KB Output is correct
25 Correct 667 ms 46992 KB Output is correct
26 Correct 667 ms 47344 KB Output is correct
27 Correct 664 ms 47300 KB Output is correct
28 Correct 668 ms 47304 KB Output is correct
29 Correct 665 ms 47360 KB Output is correct
30 Correct 679 ms 47212 KB Output is correct