萌新离散化80求调
  • 板块P1496 火烧赤壁
  • 楼主jikky
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/16 21:30
  • 上次更新2024/7/17 00:07:48
查看原帖
萌新离散化80求调
1382982
jikky楼主2024/7/16 21:30
#include<bits/stdc++.h>
using namespace std;
int ye[400004];
bool lb[400004];
//int le[4000];
int sum[4000004];
long long ans=0;
struct fire{
	int num;
	bool e;
}y[4000004];

bool cmp(fire a,fire b){
	return a.num<b.num;
}
int main(){
	int n;
	scanf("%d",&n);
	n*=2;
	for(int i=1;i<=n;i+=2){
		scanf("%d%d",&y[i],&y[i+1]);
		y[i].e=0;
		y[i+1].e=1;
	}
	sort(y+1,y+n+1,cmp);
	int cnt=1;
	for(int i=1;i<n;i++){
		if(i==1||y[i].num!=y[i-1].num){
			ye[cnt]=y[i].num;
			lb[cnt]=y[i].e;
			cnt++;
		}
	}
	for(int i=1;i<n;i++){
		y[i].num=ye[i];
		y[i].e=lb[i];
	}
	sort(y+1,y+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(y[i].e){
			sum[i]++;
		}
		else{
			sum[i]--;
		}
	}
	int l,r;
	for(int i=1;i<=n;i++){
		if(sum[i-1]!=0&&sum[i]==0) l=i-1;
		if(sum[i]!=0&&sum[i+1]==0){
			r=i;
			ans+=y[r].num-y[l].num;
		}
	}
	printf("%d",ans);
	return 0;
}
2024/7/16 21:30
加载中...