社区讨论
神奇!输出-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 条回复,欢迎继续交流。
正在加载回复...