WA #5,6,7,8 60分求助
查看原帖
WA #5,6,7,8 60分求助
664779
llxsmy_forever楼主2023/7/8 19:44
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+100;
struct Line{int x,st,ed,k;}L[N];int s[N];
struct trnode{int l,r,c,len;}tr[N];
bool cmp(Line n1,Line n2){return n1.x==n2.x?n1.k>n2.k:n1.x<n2.x;}
vector<pair<int,int> > ans;
void bt(int p,int l,int r){
	tr[p]={l,r,0,0};
	if(l+1<r){
		int mid=l+r>>1;
		bt(p<<1,l,mid);
		bt(p<<1|1,mid,r);
	}
}
void change(int p,int l,int r,int c){
	if(r<=s[tr[p].l]||l>=s[tr[p].r])return;
	if(l<=s[tr[p].l]&&r>=s[tr[p].r])tr[p].c+=c;
	else change(p<<1,l,r,c),change(p<<1|1,l,r,c);
	if(tr[p].c)tr[p].len=s[tr[p].r]-s[tr[p].l];
	else tr[p].len=(tr[p].l+1<tr[p].r)?tr[p<<1].len+tr[p<<1|1].len:0;
}
signed main(){
	int n;scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		int h,X1,X2;scanf("%lld%lld%lld",&h,&X1,&X2);
		L[i]={X1,0,h,1},L[i+n]={X2,0,h,-1};
		s[i]=0,s[i+n]=h;
	}
	n<<=1;sort(s+1,s+1+n);
	int cnt=unique(s+1,s+1+n)-(s+1);
	bt(1,1,cnt);sort(L+1,L+1+n,cmp);
	int last=0;
	for(int i=1;i<=n;i++){
		change(1,L[i].st,L[i].ed,L[i].k);
		if(tr[1].len!=last){
			ans.push_back({L[i].x,last});
			ans.push_back({L[i].x,tr[1].len});
			last=tr[1].len;
		}
	}
	printf("%lld\n",ans.size());
	for(int i=0;i<ans.size();i++){
		printf("%lld %lld\n",ans[i].first,ans[i].second);
	}
	return 0;
}
2023/7/8 19:44
加载中...