Submission #1161265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161265		asdasdqwer	Plahte (COCI17_plahte)	C++17	160 / 160	550 ms	109888 KiB

plahte

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

#define pi array<int,2>
#define pii array<pi, 2>
#define tii array<int,3>

struct BIT {
    int n;
    vector<int> bit;

    BIT(int sz) : n(sz), bit(n+1, 0) {}

    void update(int i, int v) {
        i++;
        for (;i<=n;i+=(i&(-i))) bit[i] += v;
    }

    int query(int r) {
        r++;
        int res = 0;
        for (;r>0;r-=(r&(-r))) res += bit[r];
        return res;
    }
};

map<int,int> cmp(vector<int> &dat) {
    sort(dat.begin(), dat.end());
    dat.erase(unique(dat.begin(), dat.end()), dat.end());

    map<int,int> mp;
    for (int i=0;i<(int)dat.size();i++) {
        mp[dat[i]] = i;
    }
    return mp;
}

const int BG = 80'000 * 4 + 5;
vector<tii> startRect[BG], endRect[BG], bls[BG];
set<int> col[BG];
set<pi> endSz[BG];
int parent[BG];
vector<int> child[BG];

BIT bt(BG);

signed main() {
    for (int i=0;i<BG;i++) parent[i] = -1;

    int n,m;cin>>n>>m;
    vector<pii> rect(n);
    for (auto &x:rect) cin>>x[0][0]>>x[0][1]>>x[1][0]>>x[1][1];

    vector<int> xpos, ypos;
    for (auto &x:rect) {
        for (int i=0;i<2;i++) {
            xpos.push_back(x[i][0]);
            ypos.push_back(x[i][1]);
        }
    }

    vector<tii> bll(m);
    for (auto &x:bll){
        cin>>x[0]>>x[1]>>x[2];
        xpos.push_back(x[0]);
        ypos.push_back(x[1]);
    }

    map<int,int> mp1 = cmp(xpos), mp2 = cmp(ypos);
    int cnt = 0;
    for (auto &x:rect) {
        for (int i=0;i<2;i++) {
            x[i][0] = mp1[x[i][0]];
            x[i][1] = mp2[x[i][1]];
        }

        tii inv = {x[0][1], x[1][1], cnt};
        startRect[x[0][0]].push_back(inv);
        endRect[x[1][0]].push_back(inv);
        cnt++;
    }

    for (auto &x:bll) {
        x[0] = mp1[x[0]];
        x[1] = mp2[x[1]];

        bls[x[0]].push_back(x);
    }

    for (int i=0;i<BG;i++) {
        for (auto &x:startRect[i]) {
            // determine parent
            int vl = bt.query(x[0]);
            if (vl != 0) {
                auto it = endSz[vl].lower_bound({x[0], -1});
                auto [nxt, idx] = *it;
                parent[x[2]] = idx;
            }

            // update BIT
            bt.update(x[0], 1);
            bt.update(x[1]+1, -1);
            vl++;
            endSz[vl].insert({x[1], x[2]});
        }

        for (auto &x:bls[i]) {
            int vl = bt.query(x[1]);
            if (vl == 0) continue;
            auto it = endSz[vl].lower_bound({x[1], -1});
            auto [nxt, idx] = *it;
            // cout << vl << " " << nxt << " " << idx << endl;
            col[idx].insert(x[2]);
        }

        for (auto &x:endRect[i]) {
            int vl = bt.query(x[0]);
            endSz[vl].erase(endSz[vl].find({x[1], x[2]}));
            bt.update(x[0], -1);
            bt.update(x[1]+1, 1);
        }
    }

    for (int i=0;i<n;i++) {
        if (parent[i] == -1) continue;
        child[parent[i]].push_back(i);
    }

    vector<int> ans(n, 0);
    function<void(int)> dfs=[&](int node) {
        for (auto &x:child[node]) {
            dfs(x);
            if (col[x].size() > col[node].size()) col[x].swap(col[node]);
            for (auto &y:col[x]) col[node].insert(y);
        }
        ans[node] = (int)col[node].size();
    };

    for (int i=0;i<n;i++) {
        if (parent[i] == -1) dfs(i);
    }

    for (int i=0;i<n;i++) {
        cout << ans[i] << endl;
    }
}

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