Submission #1265852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265852		huyjavalt	Plahte (COCI17_plahte)	C++20	160 / 160	341 ms	117328 KiB

plahte

#include <bits/stdc++.h>
using namespace std;

#define double long double
#define int long long

struct Line{
    int x,l,r,i,t;
    // t = 0 -> left side
    // t = 2 -> right side
    // t = 1 -> query;

    bool operator<(const Line& other) const{
        if(x == other.x) return t > other.t;
        return x < other.x;
    }
};

vector<Line> ev;
vector<int> com;

vector<int> t[1000005];

void update(int v, int tl, int tr, int l, int r, int x){
    if(l > tr || r < tl) return;
    if(l <= tl && tr <= r){
        if(x) t[v].push_back(x);
        else t[v].pop_back();
        //cout << tl << ' ' << tr << ' ' << x << ' ' << "ADD" << endl;
        return;
    }
    int tm = (tl+tr)/2;
    update(v*2,tl,tm,l,r,x);
    update(v*2+1,tm+1,tr,l,r,x);
}

int query(int v, int tl, int tr, int l, int r){
    if(l > tr || r < tl) return 0;
    if(l <= tl && tr <= r) return (t[v].size() ? t[v].back() : 0);

    int tm = (tl+tr)/2;

    int res = query(v*2,tl,tm,l,r);
    if(!res) res = query(v*2+1,tm+1,tr,l,r);
    if(!res) res = (t[v].size() ? t[v].back() : 0);
    return res;
}

vector<int> adj[800005];
set<int> col[800005];
int ans[800005];

void dfs(int v){
    for(auto u : adj[v]){
        dfs(u);
        if(col[u].size() > col[v].size()) col[v].swap(col[u]);
        for(auto i : col[u]) col[v].insert(i);
    }
    ans[v] = col[v].size();
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("squares.in","r",stdin);
//    freopen("squares.out","w",stdout);

    int n,m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        int x,y,u,v;
        cin >> x >> y >> u >> v;
        ev.push_back({x,y,v,i,2});
        ev.push_back({u,y,v,i,0});
        com.push_back(y); com.push_back(v);
    }

    for(int i = 1; i <= m; i++){
        int x,y,k;
        cin >> x >> y >> k;
        ev.push_back({x,y,y,k,1});
        com.push_back(y);
    }

    sort(com.begin(), com.end());
    sort(ev.begin(), ev.end());
    com.erase(unique(com.begin(), com.end()), com.end());

    for(auto &p : ev){
        p.l = lower_bound(com.begin(), com.end(), p.l) - com.begin() + 1;
        p.r = lower_bound(com.begin(), com.end(), p.r) - com.begin() + 1;
        //cout << p.x << ' ' << p.l << ' ' << p.r << ' ' << p.t << ' ' << p.i << endl;

        if(p.t == 2){
            int par = query(1,1,com.size(),p.l,p.r);
            update(1,1,com.size(),p.l,p.r,p.i);
            adj[par].push_back(p.i);
            //cout << par << ' ' << p.i << ' ' << "TREE" << endl;

        }
        if(p.t == 0) update(1,1,com.size(),p.l,p.r,0);
        if(p.t == 1){
            //cout << query(1,1,com.size(),p.l,p.r) << ' ' << p.i << " COL" << endl;
            col[query(1,1,com.size(),p.l,p.r)].insert(p.i);
        }
    }

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

    return 0;
}

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