P1382 不知道为什么第8个点总是WA
  • 板块学术版
  • 楼主Reunite
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/2/12 15:37
  • 上次更新2023/10/28 08:46:31
查看原帖
P1382 不知道为什么第8个点总是WA
377760
Reunite楼主2022/2/12 15:37
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

int n,cnt,num,h,l,r;
struct node{int x,h,id;}a[200005];
struct Ans{int x,y;}ans[400005];
map <int,int> mp;

void in(int &n){
    n=0;
    char c=getchar();int k=(c=='-'?-1:1);
    while(c<'0'||c>'9'){c=getchar();if(c=='-')k=-1;}
    while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
    n*=k;return ;
}

bool cmp(node p,node q){
    if(p.x!=q.x) return p.x<q.x;
    if(p.id!=q.id) return p.id<q.id;
    if(p.id==1) return p.h>q.h;
    if(p.id==0) return p.h<q.h;
}

inline void add(int h){
    if(mp.count(h)==0) mp[h]=1;
    else mp[h]++;
    return ;
}

inline void Delete(int h){
    if(mp[h]==1) mp.erase(h);
    else mp[h]--;
    return ;
}

int main(){
    in(n);
    for(int i=1;i<=n;i++){
        in(h),in(l),in(r);
        a[++cnt].x=l,a[cnt].h=h,a[cnt].id=1;
        a[++cnt].x=r,a[cnt].h=h,a[cnt].id=0;
    }
    sort(a+1,a+1+cnt,cmp);

    map <int,int> :: iterator it;
    mp[0]=1;
    for(int i=1;i<=cnt;i++){
        it=mp.end();
        it--;
        if(a[i].id==1){
            if(a[i].h<=it->first) add(a[i].h);
            else{
                num++;
                ans[num].x=a[i].x,ans[num].y=it->first;
                num++;
                ans[num].x=a[i].x,ans[num].y=a[i].h;
                add(a[i].h);
            }
        }
        else{
            if(a[i].h==it->first&&mp[a[i].h]==1){
                num++;
                ans[num].x=a[i].x,ans[num].y=a[i].h;
                mp.erase(a[i].h);
                it=mp.end();
                num++;
                it--;
                ans[num].x=a[i].x,ans[num].y=it->first;
            }
            else Delete(a[i].h);
        }
    }
    printf("%d\n",num);
    for(int i=1;i<=num;i++) printf("%d %d\n",ans[i].x,ans[i].y);

    return 0;
}
2022/2/12 15:37
加载中...