Submission #1326696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326696		tung04885	Plahte (COCI17_plahte)	C++20	0 / 160	315 ms	39952 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 80808
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define __buitin_popcount __builtin_popcountll
#define BIT(x,i) (((x)>>(i))&1ll)
#define MASK(i) (1ll<<(i))
#define left __left
#define right __right

template<class X,class Y> bool maximize(X &x,Y y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}

template<class X,class Y> bool minimize(X &x,Y y)
{
    if(y<x)
    {
        x=y;
        return 1;
    }
    return 0;
}

const int inf=1e9+412009;
const ll INF=2e18+412009;

struct POINT
{
    int x,y,color,id;

    void input()
    {
        cin>>x>>y>>color;
    }

    bool operator < (POINT other) const
    {
        return x==other.x ? y<other.y : x<other.x;
    }
};

struct STATE
{
    int x,y,id;

    bool operator < (STATE other) const
    {
        if(x==other.x&&y==other.y) return id<other.id;
        return x==other.x ? y<other.y : x<other.x;
    }
};

struct RECT
{
    int top,bot,left,right;

    void input()
    {
        int x,y,u,v;
        cin>>x>>y>>u>>v;
        top=max(y,v);
        bot=min(y,v);
        left=min(x,u);
        right=max(x,u);
    }
};

int n,m;
RECT a[MAX];
POINT paints[MAX];
int par[MAX]={};
unordered_map<int,bool> cnt[MAX];
int ans[MAX]={};

void nhap()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++) a[i].input();
    for(int i=1;i<=m;i++) paints[i].input();
}

vector<STATE> events;
set<STATE> s;
vector<int> adj[MAX];

void load_tree()
{
    vector<pii> e;

    for(int i=1;i<=n;i++)
    {
        e.push_back({a[i].left,i});
        e.push_back({a[i].right,i});
    }

    sort(all(e));

    for(pii p:e)
    {
        int id=p.se;

        if(a[id].right==p.fi)
        {
            s.erase({a[id].top,1,id});
            s.erase({a[id].bot,0,id});
            continue;
        }

        auto it1=s.lower_bound({a[id].bot,-inf,-inf});
        auto it2=it1;

        s.insert({a[id].top,1,id});
        s.insert({a[id].bot,0,id});

        if(it1==s.end()) continue;
        if(it1->x==a[id].bot)
        {
            if(it1->y==0) it1++;
            else
            {
                if(it1==s.begin()) continue;
                else it2--;
            }

            if(it1==s.end()) continue;
        }
        else
        {
            if(it1==s.begin()) continue;
            it2--;
        }

        if(it1==s.end()) continue;

        STATE up=*it1,down=*it2;

        if(up.y==down.y)
        {
            if(up.y==0) par[id]=down.id;
            else par[id]=up.id;
        }
        else
        {
            if(up.y==1) par[id]=up.id;
            else par[id]=par[up.id];
        }

        adj[par[id]].push_back(id);
    }
//
//    for(int i=1;i<=n;i++)
//    {
//        cout<<i<<": ";
//        for(int v:adj[i]) cout<<v<<' ';
//        cout<<'\n';
//    }

    s.clear();
}

bool visited[MAX]={};

void dfs(int u)
{
    visited[u]=1;
    for(int v:adj[u]) if(v!=u)
    {
        dfs(v);

        if(cnt[u].size()<cnt[v].size()) swap(cnt[u],cnt[v]);

        for(auto it:cnt[v]) cnt[u][it.fi]=1;
    }

    ans[u]=cnt[u].size();
}

void solve()
{
    load_tree();

    for(int i=1;i<=n;i++)
    {
        events.push_back({a[i].left,-inf,i});
        events.push_back({a[i].right,inf,i});
    }

    for(int i=1;i<=m;i++) events.push_back({paints[i].x,paints[i].y,paints[i].color});

    sort(all(events));

    for(STATE p:events)
    {
        int id=p.id;

        if(abs(p.y)==inf)
        {
            if(a[id].right==p.x)
            {
                s.erase({a[id].top,1,id});
                s.erase({a[id].bot,0,id});
            }
            else
            {
                s.insert({a[id].top,1,id});
                s.insert({a[id].bot,0,id});
            }

            continue;
        }

        auto it1=s.lower_bound({p.y,-inf,-inf});
        auto it2=it1;

        if(it1==s.end()) continue;
        if(it1->x==p.y)
        {
            if(it1->y==0) it1++;
            else
            {
                if(it1==s.begin()) continue;
                it2--;
            }

            if(it1==s.end()) continue;
        }
        else
        {
            if(it1==s.begin()) continue;
            it2--;
        }

        STATE up=*it1,down=*it2;

        if(up.y==down.y)
        {
            if(up.y==0) cnt[down.id][p.id]=1;
            else cnt[up.id][p.id]=1;
        }
        else
        {
            if(up.y==0) cnt[par[up.id]][p.id]=1;
            else cnt[up.id][p.id]=1;
        }
    }

    for(int i=1;i<=n;i++) if(!visited[i]) dfs(i);

    for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
//    freopen("PLAHTE.INP","r",stdin);
//    freopen("PLAHTE.OUT","w",stdout);

    nhap();
    solve();

    return 0;
}

• Subtask 1: 0 / 32
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32