Submission #1267507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267507		canhnam357	Plahte (COCI17_plahte)	C++20	160 / 160	275 ms	49004 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
pair<int, int> st[1 << 19]{};
void update(int p, int a, int b, int id, int l, int r) {
    if (l == r) {
        st[id] = {a, b};
        // cout << "UPDATED " << l << ' ' << a << ' ' << b << '\n';
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) update(p, a, b, id << 1, l, mid);
    else update(p, a, b, id << 1 | 1, mid + 1, r);
    st[id] = max(st[id << 1], st[id << 1 | 1]);
}
void find(int &ans, int p, int a, int id, int l, int r) {
    // cout << "GET " << p << ' ' << a << ' ' << l << ' ' << r << ' ' << st[id].first << '\n';
    if (l > p) return;
    if (ans != -1) return;
    if (l == r) {
        if (st[id].first >= a) {
            ans = st[id].second;
            // cout << "POS " << l << '\n';
        }
        return;
    }
    int mid = (l + r) >> 1;
    if (st[id << 1 | 1].first >= a) find(ans, p, a, id << 1 | 1, mid + 1, r);
    if (st[id << 1].first >= a) find(ans, p, a, id << 1, l, mid);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, nq;
    cin >> n >> nq;
    vector<int> ccx, ccy;
    vector<tuple<int, int, int, int>> a(n);
    for (auto &[x1, y1, x2, y2] : a) {
        cin >> x1 >> y1 >> x2 >> y2;
        assert(x1 <= x2);
        assert(y1 <= y2);
        ccx.push_back(x1);
        ccx.push_back(x2);
        ccy.push_back(y1);
        ccy.push_back(y2);
    }
    vector<tuple<int, int, int>> q(nq);
    for (auto &[x, y, k] : q) {
        cin >> x >> y >> k;
        ccx.push_back(x);
        ccy.push_back(y);
    }
    sort(all(ccx));
    ccx.erase(unique(all(ccx)), ccx.end());
    auto getx = [&](int pos) {
        return upper_bound(all(ccx), pos) - ccx.begin();
    };
    sort(all(ccy));
    ccy.erase(unique(all(ccy)), ccy.end());
    auto gety = [&](int pos) {
        return upper_bound(all(ccy), pos) - ccy.begin();
    };
    for (auto &[x1, y1, x2, y2] : a) {
        x1 = getx(x1);
        y1 = gety(y1);
        x2 = getx(x2);
        y2 = gety(y2);
    }
    for (auto &[x, y, k] : q) {
        x = getx(x);
        y = gety(y);
    }
    int m = ccx.size();
    vector<int> root(n, 1);
    vector<vector<int>> adj(n);
    vector<vector<tuple<int, int, int>>> add(m + 2), rmv(m + 2);
    vector<vector<pair<int, int>>> ball(m + 2);
    for (int i = 0; i < n; i++) {
        auto [x1, y1, x2, y2] = a[i];
        add[x1].emplace_back(y1, y2, i);
        rmv[x2 + 1].emplace_back(y1, y2, i);
    }
    for (auto [x, y, k] : q) {
        ball[x].emplace_back(y, k);
    }
    vector<vector<int>> g(n);
    int sz = ccy.size();
    {
        for (int i = 1; i <= m; i++) {
            // cout << st[1].first << ' ' << st[1].second << '\n';
            for (auto [y, y2, id] : rmv[i]) {
                update(y, 0, 0, 1, 1, sz);
            }
            for (auto [y, y2, id] : add[i]) {
                int ans = -1;
                find(ans, y, y2, 1, 1, sz);
                if (ans != -1) {
                    adj[ans].push_back(id);
                    // cout << ans << ' ' << id << '\n';
                    root[id] = 0;
                }
            }
            for (auto [y, y2, id] : add[i]) {
                update(y, y2, id, 1, 1, sz);
            }
            for (auto [y, k] : ball[i]) {
                int ans = -1;
                // cout << y << ' ' << y << "~\n";
                find(ans, y, y, 1, 1, sz);
                if (ans != -1) {
                    g[ans].push_back(k);
                }
            }
        }
    }
    vector<int> ans(n);
    function<void(int, set<int>&)> dfs = [&](int u, set<int>& st) {
        for (int v : adj[u]) {
            set<int> cs;
            dfs(v, cs);
            if (cs.size() > st.size()) swap(cs, st);
            for (int i : cs) st.insert(i);
        }
        for (int i : g[u]) st.insert(i);
        ans[u] = st.size();
    };
    set<int> st;
    for (int i = 0; i < n; i++) {
        if (root[i]) {
            st.clear();
            dfs(i, st);
        }
    }
    for (int i : ans) cout << i << '\n';
    return 0;
}

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