Submission #1124392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124392		Zero_OP	Plahte (COCI17_plahte)	C++20	160 / 160	225 ms	31180 KiB

plahte

#include <bits/stdc++.h>

using namespace std;

struct segment_tree{
    vector<int> st, lazy;
    segment_tree(int n) : st(n << 2, -1), lazy(n << 2, -2) {}

    void apply(int id, int c){
        st[id] = c;
        lazy[id] = c;
    }

    void down(int id){
        if(lazy[id] != -2){
            apply(id << 1, lazy[id]);
            apply(id << 1 | 1, lazy[id]);
            lazy[id] = -2;
        }
    }

    void update(int id, int l, int r, int u, int v, int c){
        if(u <= l && r <= v) apply(id, c);
        else{
            int mid = l + r >> 1;
            down(id);
            if(u <= mid) update(id << 1, l, mid, u, v, c);
            if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, c);

        }
    }

    int query(int id, int l, int r, int pos){
        if(l == r) return st[id];
        int mid = l + r >> 1;
        down(id);
        if(pos <= mid) return query(id << 1, l, mid, pos);
        else return query(id << 1 | 1, mid + 1, r, pos);
    }
};

struct event{
    int x, l, r, type, id;
    event(int x, int l, int r, int type, int id) : x(x), l(l), r(r), type(type), id(id) {}
    bool operator < (const event& o){ return make_pair(x, -type) < make_pair(o.x, -o.type); }
};

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

 //   freopen("LOANGMUC.inp", "r", stdin);
 //   freopen("LOANGMUC.out", "w", stdout);

    int N, Q;
    cin >> N >> Q;

    vector<vector<int>> adj(N);
    vector<event> events;
    vector<int> Oy;
    for(int i = 0; i < N; ++i){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1 > x2) swap(x1, x2);
        if(y1 > y2) swap(y1, y2);
        Oy.emplace_back(y1);
        Oy.emplace_back(y2);
        events.push_back(event(x1, y1, y2, +1, i));
        events.push_back(event(x2, y1, y2, -1, i));
    }

    vector<int> colors;

    for(int i = 0; i < Q; ++i){
        int x, y, k;
        cin >> x >> y >> k;
        Oy.emplace_back(y);
        events.push_back(event(x, y, y, 0, k));
    }

    sort(Oy.begin(), Oy.end());
    Oy.erase(unique(Oy.begin(), Oy.end()), Oy.end());
    sort(events.begin(), events.end());

    int ys = (int)Oy.size();
    segment_tree tr(ys);

    vector<int> par(N, -1);
    vector<set<int>> st(N);

    vector<bool> is_root(N, true);

    for(auto [x, l, r, type, id] : events){
        l = lower_bound(Oy.begin(), Oy.end(), l) - Oy.begin();
        r = lower_bound(Oy.begin(), Oy.end(), r) - Oy.begin();
        if(type == +1){
            par[id] = tr.query(1, 0, ys - 1, l);
            tr.update(1, 0, ys - 1, l, r, id);
            if(par[id] != -1){
                is_root[id] = false;
                adj[par[id]].emplace_back(id);
            }
        } else if(type == 0){
            int c = tr.query(1, 0, ys - 1, l);
            if(c != -1){
                st[c].insert(id);
            }
        } else if(type == -1){
            tr.update(1, 0, ys - 1, l, r, par[id]);
        } else assert(false);
    }


    vector<int> ans(N);
    function<void(int)> dfs = [&](int u){
        for(auto v : adj[u]){
            dfs(v);
            if((int)st[u].size() < st[v].size()) swap(st[u], st[v]);
            for(auto x : st[v]) st[u].insert(x);
        }
        ans[u] = (int)st[u].size();
    };

    for(int i = 0; i < N; ++i){
        if(is_root[i]) dfs(i);
    }

    for(int i = 0; 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