80分,WA #8 #9求助
  • 板块P1382 楼房
  • 楼主Phoenix_2010
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/16 19:33
  • 上次更新2024/1/16 19:42:36
查看原帖
80分,WA #8 #9求助
713914
Phoenix_2010楼主2024/1/16 19:33
#include<bits/stdc++.h>
#define mid (l+r)/2
using namespace std;
const int N=1e5+5;
int n,m,h[N],l[N],r[N],a[2*N],t[8*N],cnt,last,x[N],y[N];
void lsh()
{
	sort(a+1,a+2*n+1);m=unique(a+1,a+2*n+1)-a-1;
	for(int i=1;i<=n;i++) l[i]=lower_bound(a+1,a+m+1,l[i])-a,r[i]=lower_bound(a+1,a+m+1,r[i])-a;
}
void pushdown(int p){t[p*2]=max(t[p*2],t[p]),t[p*2+1]=max(t[p*2+1],t[p]);}
void upd(int p,int l,int r,int ql,int qr,int x)
{
	if(l==ql&&r==qr){t[p]=max(t[p],x);return;}
	pushdown(p);
	if(qr<=mid) upd(p*2,l,mid,ql,qr,x);
	else if(ql>mid) upd(p*2+1,mid+1,r,ql,qr,x);
	else upd(p*2,l,mid,ql,mid,x),upd(p*2+1,mid+1,r,mid+1,qr,x);
}
int query(int p,int l,int r,int qi)
{
	if(l==r) return t[p];
	pushdown(p);
	if(qi<=mid) return query(p*2,l,mid,qi);
	else return query(p*2+1,mid+1,r,qi);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d%d%d",&h[i],&l[i],&r[i]),a[2*i-1]=l[i],a[2*i]=r[i];
	lsh();
	for(int i=1;i<=n;i++) upd(1,1,m,l[i],r[i]-1,h[i]);
	x[++cnt]=a[1],y[cnt]=0;
	for(int i=1;i<m;i++)
	{
		int tmp=query(1,1,m,i);
		if(tmp!=last) x[++cnt]=a[i],y[cnt]=tmp,x[++cnt]=a[i+1],y[cnt]=tmp;
		else x[cnt]=a[i+1];
		last=tmp;
	}
	x[++cnt]=a[m],y[cnt]=0;
	cout<<cnt<<endl;for(int i=1;i<=cnt;i++) printf("%d %d\n",x[i],y[i]);
	return 0;
}
2024/1/16 19:33
加载中...