求助关于离散化做法数组开多大
查看原帖
求助关于离散化做法数组开多大
235901
Always_Remember_It楼主2023/9/20 17:45
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,l[N],r[N];
int now[N],cnt,c[N],b[N],sum[N];
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=(s<<3)+(s<<1)+(ch^48);
		ch=getchar();
	}
	return s*f;
}
signed main(){
	cin>>n;
	set<int> s;
	for(int i=1;i<=n;i++){
		cin>>l[i]>>r[i];
		--r[i];
		s.insert(l[i]);
		s.insert(r[i]);
	}
	int len=s.size();
	for(int i=1;i<=len;i++){
		int num=*s.begin();
		now[++cnt]=num;
		c[cnt]=num;
		s.erase(num);
	}
	for(int i=1;i<=n;i++){
		int pl=lower_bound(now+1,now+cnt+1,l[i])-now;
		int pr=lower_bound(now+1,now+cnt+1,r[i])-now;
		l[i]=pl;
		r[i]=pr;
	}
	for(int i=1;i<=n;i++){
		int lt=c[l[i]]+cnt+1,rt=c[r[i]]+cnt+1;
		++b[lt];
		--b[rt+1];
	}
	for(int i=1;i<N;i++){
		sum[i]=sum[i-1]+b[i];
	}
	int tot=0;
	for(int i=1;i<N;i++){
		if(sum[i]) ++tot;
	}
	cout<<tot<<endl;
	return 0;
}
开1e5 WA 1个 RE 1个
开到2e6还RE了1个,请问这是为什么
2023/9/20 17:45
加载中...