CCPC - Exam Results

题目链接：CCPC - Exam Results

---

我们先按照最大值从小到大排序，然后枚举作为最大值的值。

如果满足后面 最小值的max，这个答案就是合法的。然后对于前面做一个尺取维护答案，对于后面的就是一个线段树区间查询。

然后枚举某个的最小值作为最大值，我们可以发现必然是最大值最小值才合法，然后线性遍历即可。

---

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10,M=N*40,up=1e9;
int n,P,m,lc[M],rc[M],sum[M],rt,cnt,res,mx[N],pos,ts;
struct node{int a,b;}t[N];
#define mid (l+r>>1)
void change(int &p,int l,int r,int x,int v){
	if(!p) p=++cnt,lc[p]=rc[p]=sum[p]=0;
	if(l==r){sum[p]+=v; return ;}
	if(x<=mid) change(lc[p],l,mid,x,v);
	else change(rc[p],mid+1,r,x,v);
	sum[p]=sum[lc[p]]+sum[rc[p]];
}
int ask(int p,int l,int r,int ql,int qr){
	if(!p) return 0;
	if(l==ql&&r==qr) return sum[p];
	if(qr<=mid) return ask(lc[p],l,mid,ql,qr);
	else if(ql>mid) return ask(rc[p],mid+1,r,ql,qr);
	else return ask(lc[p],l,mid,ql,mid)+ask(rc[p],mid+1,r,mid+1,qr);
}
inline void solve(){
	rt=cnt=0; lc[0]=rc[0]=sum[0]=0; res=1; pos=1;
	scanf("%d %d",&n,&P); mx[n+1]=0;
	for(int i=1;i<=n;i++){
		scanf("%d %d",&t[i].a,&t[i].b);
		if(t[i].a>t[i].b) swap(t[i].a,t[i].b);
	}
	sort(t+1,t+1+n,[](node a,node b){return a.b<b.b;});
	mx[n]=t[n].a;
	for(int i=n-1;i>=1;i--) mx[i]=max(mx[i+1],t[i].a);
	for(int i=1;i<=n;i++) change(rt,1,up,t[i].a,1);
	for(int i=1;i<=n;i++){
		change(rt,1,up,t[i].a,-1);
		if(t[i].b<mx[i+1]) continue;
		int lim=(1LL*t[i].b*P+99)/100;
		while(t[pos].b<lim) pos++;
		res=max(res,i-pos+1+ask(rt,1,up,lim,up));
	}
	sort(t+1,t+1+n,[](node a,node b){return a.a<b.a;});
	int lim=(1LL*t[n].a*P+99)/100,ans=0;
	for(int i=1;i<=n;i++){
		if(t[i].b>t[n].a){
			if(t[i].a>=lim) ans++;
		}else if(t[i].b>=lim) ans++;
	}
	printf("Case #%d: %d\n",++ts,max(ans,res));
}
signed main(){
	int T; cin>>T; while(T--) solve();
	return 0;
}

本文地址：https://blog.csdn.net/weixin_43826249/article/details/109256391