CompetitiveProgramming/he.cpp at main · darksidergod/CompetitiveProgramming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>

using namespace std;
#define ll long long int
#define SIZE (ll)5e6
ll n, a[SIZE];

void func(ll key)
{
	ll lo=0, hi=n-1, mid=lo+(hi-lo)/2;
	if(a[hi]<key){ cout<<0<<"\n"; return;}
	if(a[lo]>=key){ cout<<n<<"\n"; return;}
	while(lo<hi)
	{
		mid = lo + (hi-lo)/2;

		if(a[mid]<key) lo=mid+1;

		else hi=mid;
	}

	if(a[lo]>=key) { cout<<n-lo<<"\n";}

	else if(a[mid]>=key) { cout<<n-mid<<"\n";}

	else if(a[hi]>=key) { cout<<n-hi<<"\n";}

	return;
}

int main(void)
{
	ll m, q;
	cin>>n;
	cin>>m;
	memset(a, 0, sizeof(a));

	for(ll i=0; i<m; i++)
	{
		ll u, v;
		cin>>u>>v;
		u--; v;
		a[u]++;
		if(v<n) a[v]--;
	}

	for(ll i=1; i<n; i++)
		a[i]+=a[i-1];
	sort(a, a+n);
	cin>>q;
	for(ll id=0; id<q; id++)
	{
		ll x, ans;
		cin>>x;
		func(x);
	}

	return 0;

}