Submission #1124774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124774		GasmaskChan	Plahte (COCI17_plahte)	C++17	160 / 160	345 ms	47944 KiB

plahte

#include <bits/stdc++.h>

using namespace std;
#define ll long long

const int MAX = 8e4 + 5;
struct rec {
    int x1, y1, x2, y2;
};

struct ink {
    int x, y, k;
};

rec a[MAX];
ink drops[MAX];

struct SMT {
    int n;
    vector<vector<int>> ST;

    SMT(int n) : n(n) {
        int sz = __lg(n) + 2;
        ST.resize(1 << sz);
    }

    void update(int id, int l, int r, const int &u, const int &v, const int &idx) {
        if (v < l || r < u) return;
        if (u <= l && r <= v) {
            if (idx == -1) ST[id].pop_back();
            else ST[id].push_back(idx);
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, idx);
        update(id << 1 | 1, mid + 1, r, u, v, idx);
    }

    void update(const int &l, const int &r, const int &idx) {
        update(1, 1, n, l, r, idx);
    }

    int get(int id, int l, int r, const int &u, const int &v) {
        if (v < l || r < u) return 0;
        if (u <= l && r <= v) return ST[id].empty() ? 0 : ST[id].back();
        int mid = (l + r) >> 1;
        int L = get(id << 1, l, mid, u, v);
        int R = get(id << 1 | 1, mid + 1, r, u, v);

        int cubu = ST[id].empty() ? 0 : ST[id].back();
        if (a[L].x1 > a[cubu].x1) cubu = L;
        if (a[R].x1 > a[cubu].x1) cubu = R;

        return cubu;
    }

    int get(const int &l, const int &r) {
        return get(1, 1, n, l, r);
    }
};

struct event {
    int x, l, r, type, id;
    bool operator < (const event &other) const {
        if (x != other.x) return x < other.x;
        return type < other.type;
    }
};

vector<int> nenY;
vector<event> events;

int ans[MAX];
vector<int> g[MAX];
unordered_set<int> mp[MAX];

void dfs(int u) {
    for (int &v : g[u]) {
        dfs(v);
        if (mp[u].size() < mp[v].size()) swap(mp[u], mp[v]);
        for (auto &i : mp[v]) {
            mp[u].insert(i);
        }
    }
    ans[u] = (int)mp[u].size();
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
        nenY.push_back(a[i].y1), nenY.push_back(a[i].y2);
    }

    for (int i = 1; i <= m; i++) {
        cin >> drops[i].x >> drops[i].y >> drops[i].k;
        nenY.push_back(drops[i].y);
    }

    sort(nenY.begin(), nenY.end());
    nenY.erase(unique(nenY.begin(), nenY.end()), nenY.end());

    for (int i = 1; i <= n; i++) {
        a[i].y1 = lower_bound(nenY.begin(), nenY.end(), a[i].y1) - nenY.begin() + 1;
        a[i].y2 = lower_bound(nenY.begin(), nenY.end(), a[i].y2) - nenY.begin() + 1;

        events.push_back({a[i].x1, a[i].y1, a[i].y2, 1, i});
        events.push_back({a[i].x2, a[i].y1, a[i].y2, 3, i});
    }

    for (int i = 1; i <= m; i++) {
        drops[i].y = lower_bound(nenY.begin(), nenY.end(), drops[i].y) - nenY.begin() + 1;
        events.push_back({drops[i].x, drops[i].y, drops[i].y, 2, drops[i].k});
    }


    sort(events.begin(), events.end());

    SMT sech((int)nenY.size());

    for (auto &[x, l, r, type, id] : events) {
        if (type == 1) {
            int j = sech.get(l, r);
            g[j].push_back(id);
            sech.update(l, r, id);
        }
        else if (type == 2) {
            int j = sech.get(l, r);
            mp[j].insert(id);
        }
        else {
            sech.update(l, r, -1);
        }
    }

    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