Submission #1069571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069571		Perl32	Plahte (COCI17_plahte)	C++17	160 / 160	541 ms	79044 KiB

plahte

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

struct Info {
    int v = -1;
    Info() = default;
    Info(int v) : v(v) {}
};

Info operator+(const Info &a, const Info &b) {
    Info ret;
    return ret;
}

struct Tag {
    bool st = false;
    int add = -1;

    Tag() = default;
    explicit Tag(int v) {
        st = true;
        add = v;
    }
};

void apply(Info &a, Tag b) {
    if (b.st) {
        a.v = b.add;
    }
}

void apply(Tag &a, Tag b) {
    if (b.st) a = b;
}

template<class Info, class Tag, class Merge = plus<Info>>
class LazySegTree {
 public:
    int sz;
    const Merge merge;
    vector<Info> t;
    vector<Tag> tag;

    LazySegTree() = default;

    LazySegTree(int n, const Info &v = Info()) : merge(Merge()) {
        sz = 1;
        while (sz < n) sz <<= 1;
        t.assign(sz << 1, Info());
        tag.assign(sz << 1, {});
        for (int i = 0; i < n; ++i) {
            t[i + sz] = v;
        }
        for (int i = sz - 1; i > 0; --i) {
            pull(i);
        }
    }

    LazySegTree(const vector<Info> &a) : merge(Merge()) {
        sz = 1;
        while (sz < szof(a)) sz <<= 1;
        t.resize(sz << 1), tag.assign(sz << 1, {});
        for (int i = 0; i < int(a.size()); ++i) {
            t[i + sz] = a[i];
        }
        for (int i = sz - 1; i > 0; --i) {
            pull(i);
        }
    }

    void pull(int x) {
        t[x] = merge(t[x << 1], t[x << 1 | 1]);
    }

    void apply(int p, const Tag &v) {
        ::apply(t[p], v);
        ::apply(tag[p], v);
    }

    void push(int x) {
        apply(x << 1, tag[x]);
        apply(x << 1 | 1, tag[x]);
        tag[x] = Tag();
    }

    void modify(int i, const Info v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            t[x] = v;
            return;
        }
        int m = (lx + rx) >> 1;
        push(x);
        if (i < m) {
            modify(i, v, x << 1, lx, m);
        } else {
            modify(i, v, x << 1 | 1, m, rx);
        }
        pull(x);
    }

    void modify(int p, const Info v) {
        modify(p, v, 1, 0, sz);
    }

    Info query(int i, int x, int lx, int rx) {
        if (lx + 1 == rx) return t[x];
        int m = (lx + rx) >> 1;
        push(x);
        if (i < m) return query(i, x << 1, lx, m);
        return query(i, x << 1 | 1, m, rx);
    }

    Info query(int i) {
        return query(i, 1, 0, sz);
    }

    Info rangeQuery(int l, int r, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return Info();
        }
        if (l <= lx && rx <= r) {
            return t[x];
        }
        int m = (lx + rx) >> 1;
        push(x);
        return merge(rangeQuery(l, r, x << 1, lx, m), rangeQuery(l, r, x << 1 | 1, m, rx));
    }

    Info rangeQuery(int l, int r) {
        return rangeQuery(l, r, 1, 0, sz);
    }

    void rangeApply(int l, int r, const Tag v, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return;
        }
        if (l <= lx && rx <= r) {
            apply(x, v);
            return;
        }
        int m = (lx + rx) >> 1;
        push(x);
        rangeApply(l, r, v, x << 1, lx, m);
        rangeApply(l, r, v, x << 1 | 1, m, rx);
        pull(x);
    }

    void rangeApply(int l, int r, Tag v) {
        rangeApply(l, r, v, 1, 0, sz);
    }
};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> sx, sy;
    vector<array<int, 2>> c(n);
    unordered_map<int, vector<int>> op, cl;
    for (int i = 0; i < n; ++i) {
        array<int, 2> l, r;
        for (auto& x : l) cin >> x;
        for (auto& x : r) cin >> x;
        sx.push_back(l[0]);
        sy.push_back(l[1]);
        sx.push_back(r[0]);
        sy.push_back(r[1]);
        c[i] = {l[1], r[1]};
        op[l[0]].push_back(i);
        cl[r[0]].push_back(i);
    }
    unordered_map<int, vector<pair<int, int>>> qry;
    while (q--) {
        int x, y, clr;
        cin >> x >> y >> clr;
        sx.push_back(x);
        sy.push_back(y);
        qry[x].push_back({y, clr});
    }
    sort(sx.begin(), sx.end());
    sx.resize(unique(sx.begin(), sx.end()) - sx.begin());
    sort(sy.begin(), sy.end());
    sy.resize(unique(sy.begin(), sy.end()) - sy.begin());
    for (auto& [l, r] : c) {
        l = lower_bound(sy.begin(), sy.end(), l) - sy.begin();
        r = lower_bound(sy.begin(), sy.end(), r) - sy.begin();
    }
    vector<vector<int>> g(n);
    vector<int> par(n, -1);
    vector<vector<int>> a(n);
    LazySegTree<Info, Tag> st(sy.size());
    for (int x : sx) {
        for (int i : op[x]) {
            par[i] = st.query(c[i][0]).v;
            if (par[i] != -1) {
                g[par[i]].push_back(i);
            }
            st.rangeApply(c[i][0], c[i][1] + 1, Tag(i));
        }
        for (auto [y, clr] : qry[x]) {
            int id = st.query(lower_bound(sy.begin(), sy.end(), y) - sy.begin()).v;
            if (id != -1) {
                a[id].push_back(clr);
            }
        }
        for (int i : cl[x]) {
            st.rangeApply(c[i][0], c[i][1] + 1, Tag(par[i]));
        }
    }
    vector<set<int>> kek(n);
    vector<int> ans(n, 0);
    auto Dfs = [&](auto&& self, int u) -> void {
        for (auto to : g[u]) {
            self(self, to);
            if (kek[u].size() < kek[to].size()) swap(kek[u], kek[to]);
            while (!kek[to].empty()) {
                kek[u].insert(*kek[to].begin()), kek[to].erase(kek[to].begin());
            }
        }
        for (auto x : a[u]) kek[u].insert(x);
        ans[u] = (int) kek[u].size();
    };
    for (int i = 0; i < n; ++i) {
        if (par[i] == -1) {
            Dfs(Dfs, i);
        }
    }
    for (auto x : ans) cout << x << '\n';
    return 0;
}

/*

 */

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