社区讨论

神奇!输出-9999

P1382楼房参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi6tdodf
此快照首次捕获于
2025/11/20 10:30
4 个月前
此快照最后确认于
2025/11/20 10:30
4 个月前
查看原帖
CPP
#include<cstdio>
#include<algorithm>
#include<cstring>
#define lson o<<1
#define rson o<<1|1
#define mid (l+r)/2
using namespace std;
struct Node
{
	int left;
	int right;
	int height;
}a[100005];
struct Tree
{
	int setv;
	bool flag;
}tree[400005];
struct Place
{
	int place;
	int lorr;
	int x,y;
}p[200005];
int n,num,h[200005],rank[200005],ans[400005][2];
bool cmp1(Place x,Place y)
{
	return x.x<y.x;
}
bool cmp2(Node x,Node y)
{
	return x.height<y.height;
}
void pushdown(int o,int len)
{
	if(len==1)return;
	if(tree[o].flag)
	{
		tree[lson].flag=1;
		tree[rson].flag=1;
		tree[lson].setv=tree[o].setv;
		tree[rson].setv=tree[o].setv;
		tree[o].flag=0;
	}
}
void set(int o,int l,int r,int from,int to,int value)
{
	if(l>=from&&r<=to)
	{
		tree[o].flag=1;
		tree[o].setv=value;
		return;
	}
	pushdown(o,r-l+1);
	if(from<=mid)set(lson,l,mid,from,to,value);
	if(to>mid)set(rson,mid+1,r,from,to,value);
}
void work(int o,int l,int r)
{
	if(tree[o].flag)
	{
		for(int i=l;i<=r;i++)
		  h[i]=tree[o].setv;
		return;
	}
	if(l==r)return;
	work(lson,l,mid);
	work(rson,mid+1,r);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a[i].height,&a[i].left,&a[i].right);
		p[++num].x=a[i].left;
		p[num].lorr=0;
		p[num].place=i;
		p[++num].x=a[i].right;
		p[num].lorr=1;
		p[num].place=i;
	}
	sort(p+1,p+num+1,cmp1);
	rank[1]=p[1].x;
	p[1].y=1;
	int now=1;
	for(int i=2;i<=num;i++)
	{
		if(p[i].x==p[i-1].x)
		{
			p[i].y=p[i-1].y;
			continue;
		}
		p[i].y=++now;
		rank[now]=p[i].x;
	}
	for(int i=1;i<=num;i++)
	{
		if(p[i].lorr==0) a[p[i].place].left=p[i].y;
		else a[p[i].place].right=p[i].y;
	}
	sort(a+1,a+n+1,cmp2);
//	for(int i=1;i<=now;i++)
//	  printf("%d:%d\n",i,rank[i]);
	for(int i=1;i<=n;i++)
	  set(1,1,now,a[i].left,a[i].right-1,a[i].height);
	work(1,1,now);
	num=0;
	for(int i=1;i<=now;i++)
	{
		if(h[i]!=h[i-1])
		{
			ans[++num][0]=rank[i];
			ans[num][1]=h[i-1];
			ans[++num][0]=rank[i];
			ans[num][1]=h[i];
		}
	}
	printf("%d\n",num);
	for(int i=1;i<=num;i++)
	  printf("%d %d\n",ans[i][0],ans[i][1]);
	return 0;
}
测试点8:On line 164919 column 11, read -9999, expected 0. 得分0

回复

4 条回复,欢迎继续交流。

正在加载回复...