Submission #968533

#	Time	Username	Problem	Language	Result	Execution time	Memory
968533		penguin133	Index (COCI21_index)	C++17	110 / 110	687 ms	47360 KiB

index

// 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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50