Submission #649503

#	Time	Username	Problem	Language	Result	Execution time	Memory
649503		NintsiChkhaidze	Index (COCI21_index)	C++14	110 / 110	1002 ms	82012 KiB

index

#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define pii pair <int,int>
using namespace std;
 
const int N = 200005,m = 200000;

struct node {
	int l,r,val;
	node (){
		l = r = val = 0;
	}
};

int root[N],Nodes,lf,rg,a[N];
node t[32 * N];

int upd(int id,int l,int r,int pos){
	t[++Nodes] = t[id];
	id = Nodes;

	if (l == r){
		t[id].val++;
	}else{
		int mid = (l+r)/2;
		if(pos > mid) t[id].r = upd(t[id].r, mid + 1,r, pos);
		else t[id].l = upd(t[id].l, l, mid, pos);
		t[id].val = t[t[id].l].val + t[t[id].r].val;
	}

	return id;
}

int get(int id1, int id2,int l,int r,int L,int R){
	if (r < L || R < l) return 0;
	if (L <= l && r <= R) return t[id2].val - t[id1].val;
	int mid = (l+r)/2;
	return get(t[id1].l, t[id2].l, l, mid, L, R) + get(t[id1].r, t[id2].r, mid + 1, r, L, R);
}

bool check(int x){
	int k = get(root[lf - 1], root[rg], 1, m, x, m);
	return (k >= x);
}
int main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n,q;
	cin>>n>>q;

	for (int i = 1; i <= n; i++){
		cin>>a[i];
		root[i] = upd(root[i - 1], 1, m, a[i]);
	}
	
	while (q--){
		cin>>lf>>rg;

		int l=1,r = m,res=0;
		while (l <= r){
			int mid = (l + r)>>1;
			if (check(mid)) res = mid,l = mid + 1;
			else r = mid - 1;
 		}
		cout<<res<<"\n";
	}
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50