我是蒟蒻,橙题都要求调
  • 板块P1496 火烧赤壁
  • 楼主linch吃瓜猫
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/11/28 21:24
  • 上次更新2024/11/28 23:24:20
查看原帖
我是蒟蒻,橙题都要求调
737242
linch吃瓜猫楼主2024/11/28 21:24

感觉不止橙。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
long long n,a[maxn],b[maxn],c[maxn],v[maxn],pre[maxn],ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		c[i]=a[i];c[i+n]=b[i];
	}
	sort(c+1,c+2*n+1);
	int k=unique(c+1,c+2*n+1)-c;
	for(int i=1;i<=n;i++){
		int x=lower_bound(c+1,c+k+1,a[i])-c;
		int y=lower_bound(c+1,c+k+1,b[i])-c;
		v[x]++;
		v[y]--;
	}
	for(int i=1;i<k;i++){
		pre[i]=pre[i-1]+v[i];
		if(pre[i]>=1) ans+=c[i+1]-c[i];
	}
	cout<<ans<<"\n";
	return 0;
}

60pts:https://www.luogu.com.cn/record/191718671

2024/11/28 21:24
加载中...