wa0pts求调
  • 板块P1382 楼房
  • 楼主kingho11
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/29 20:05
  • 上次更新2024/7/29 20:17:06
查看原帖
wa0pts求调
562569
kingho11楼主2024/7/29 20:05
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,cnt;
struct del_heap{
    priority_queue <int,vector<int>,less<int> > a,b;
    void Push(int x)
    {
        a.push(x);
    }
    void Erase(int x)
    {
        b.push(x);
    }
    void Pop()
    {
        while(!a.empty() && !b.empty() && a.top()==b.top())
        {
            a.pop(),b.pop();
        }
        a.pop();
    }
    int Top()
    {
        while(!a.empty() && !b.empty() && a.top()==b.top())
        {
            a.pop(),b.pop();
        }
        if(a.empty())
        {
            return 0;
        }
        return a.top();
    }
    int Top2()
    {
        int o=Top();
        Pop();
        int tp2=Top();
        Push(o);
        return tp2;
    }
}pq;
void print()
{
    del_heap u;
    while(pq.Top())
    {
        int o=pq.Top();
        cout<<o<<" ";
        u.Push(o);
        pq.Pop();
    }
    while(u.Top())
    {
        int o=u.Top();
        pq.Push(o);
        u.Pop();
    }
    cout<<"\n";
}
struct uuu{
    int h,x;
    bool b1;
}a[N];
bool cmp(uuu a,uuu b)
{
    if(a.x<b.x)
    {
        return true;
    }else if(a.x>b.x)
    {
        return false;
    }else
    {
        if(a.h>b.h)
        {
            return true;
        }else
        {
            return false;
        }
    }
}
vector <pair<int,int> > v;
int cida;
void complete(int lx,int ly,int x,int y)
{
    // cout<<"  "<<lx<<" "<<ly<<" "<<x<<" "<<y<<"\n";
    if(ly==y)
    {
        v.push_back(make_pair(x,y));
        return ;
    }
    int tp=pq.Top();
    pq.Pop();
    int o=pq.Top();
    pq.Push(tp);
    if(o==0)
    {
        o=cida;
    }
    if(o!=ly)
    {
        v.push_back(make_pair(lx,cida));
    }
    v.push_back(make_pair(x,o));
    if(o!=y)
    {
        v.push_back(make_pair(x,y));
    }
}
void solve(uuu u)
{
    bool fl=false;
    if(u.b1)
    {
        pq.Push(u.h);
    }else
    {
        fl=true;
    }
    // print();
    if(pq.Top()!=u.h)
    {
        return ;
    }
    int lx=v.back().first,ly=v.back().second;
    complete(lx,ly,u.x,u.h);
    cida=pq.Top2();
    if(fl)
    {
        pq.Erase(u.h);
    }
}
int main()
{
    cin>>n;
    int h,l,r;
    for(int i=1;i<=n;i++)
    {
        cin>>h>>l>>r;
        a[++cnt].x=l,a[cnt].h=h,a[cnt].b1=true;
        a[++cnt].x=r,a[cnt].h=h,a[cnt].b1=false;
    }
    sort(a+1,a+1+cnt,cmp);
    v.push_back(make_pair(a[1].x,0));
    v.push_back(make_pair(a[1].x,a[1].h));
    pq.Push(a[1].h);
    for(int i=2;i<=cnt;i++)
    {
        solve(a[i]);
    }
    v.push_back(make_pair(a[cnt].x,0));
    cout<<v.size()<<"\n";
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i].first<<" "<<v[i].second<<"\n";
    }
}
2024/7/29 20:05
加载中...