https://vjudge.net/problem/Gym-102769E
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll ans[800005], diff[800005];
ll a[200005], b[200005];
ll res;
void solve()
{
res = 0;
ll n, p, cnt = 0, maxb = 0;
scanf("%lld%lld", &n, &p);
for (ll i = 0; i <= 4 * n + 2; ++i)
diff[i] = 0;
for (ll i = 0; i < n; ++i)
{
scanf("%lld%lld", &a[i], &b[i]);
ans[cnt++] = b[i], ans[cnt++] = b[i] * 100 / p;
ans[cnt++] = a[i], ans[cnt++] = a[i] * 100 / p;
if (b[i] > maxb)
maxb = b[i];
}
sort(ans, ans + cnt); // logn
//对于每一个分数,都有一个 使他及格的 分数上限和分数下限,在这个区间内的所有分数都可以使它及格
//及格就让这个区间内的每个分数对应的及格人数+1(用差分数组这个时间复杂度为O(1))
for (ll i = 0; i < n; ++i)
{ // nlogn //把符合的区间人数+1
ll minn = b[i];
ll pos1 = lower_bound(ans, ans + cnt, minn) - ans; //低分数下限
ll minm = b[i] * 100 / p;
ll pos2 = lower_bound(ans, ans + cnt, minm) - ans; //低分数上限
ll maxn = a[i];
ll pos3 = lower_bound(ans, ans + cnt, maxn) - ans; //高分数下限
ll maxm = a[i] * 100 / p;
ll pos4 = lower_bound(ans, ans + cnt, maxm) - ans; //高分数上限
if (pos2 < pos3)
{// [pos1,pos2] 和 [pos3,pos4] 区间内+1
++diff[pos1], --diff[pos2 + 1];
++diff[pos3], --diff[pos4 + 1];
}
else
{//[pos1,pos4]区间内+1
++diff[pos1], --diff[pos4 + 1];
}
}
//现在每个分数对应的及格人数有了,遍历一遍分数找到及格最多的人数即可
ll sum=0;
for (ll i = 0; i < cnt; ++i)
{
sum += diff[i];
//保证取到的是最高分(最小的最高分是：b值得最大值)
if (ans[i] >= maxb )
res =max(sum,res);
}
}
int main()
{
int t;
scanf("%d", &t);
for (int i = 1; i <= t; i++)
{
solve();
printf("Case #%d: %lld\n", i, res);
}
return 0;
}