Submission #1177927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177927		cheat_when_I_was_young	Plahte (COCI17_plahte)	C++17	0 / 160	185 ms	76936 KiB

plahte

#include "bits/stdc++.h"
#ifdef LOCAL
#include "windows.h"
#include "psapi.h"
#endif
using namespace std;
bool Multitest();
void Init();
void Nguyen_Tuong_Duy();
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(ios::badbit | ios::failbit);
    #ifdef LOCAL
        PROCESS_MEMORY_COUNTERS pmc;
        auto start_time = chrono::high_resolution_clock::now();
        GetProcessMemoryInfo(GetCurrentProcess(), &pmc, sizeof(pmc));
        auto start_memory = pmc.PeakWorkingSetSize;
    #endif
    int TEST = 1;
    if (Multitest()) cin >> TEST;
    Init();
    while (TEST--) Nguyen_Tuong_Duy();
    #ifdef LOCAL
        auto end_time = chrono::high_resolution_clock::now();
        GetProcessMemoryInfo(GetCurrentProcess(), &pmc, sizeof(pmc));
        auto end_memory = pmc.PeakWorkingSetSize;
        auto used_time = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
        auto used_memory = (end_memory - start_memory) / 1048576.0;
        cerr << "\nUsed: " << used_time << " ms, ";
        cerr << fixed << setprecision(3) << used_memory << " MB\n\n";
    #endif
}

bool Multitest() {
    return 0;
}

void Init() {
}

struct rectangle {
    int x1, y1, x2, y2;
};

struct line {
    int y1, y2, i;
    bool operator < (const line &o) const {
        return tie(y1, y2, i) < tie(o.y1, o.y2, o.i);
    }
};

struct point {
    int x, y, c;
};

struct event {
    int x, i;
    bool is_line, is_begin;
    bool operator < (const event &o) const {
        if (x != o.x) return x < o.x;
        if (is_line && !o.is_line) return is_begin;
        else if (!is_line && o.is_line) return !o.is_begin;
        return false;
    }
};

struct lazy_dynamic_segment_tree {
    struct node {
        int val = -1, lazy = INT_MIN;
        int l = -1, r = -1;
    };
    int L, R;
    vector<node> t;
    int new_node() {
        int n = t.size();
        t.emplace_back();
        return n;
    }
    lazy_dynamic_segment_tree(int L, int R): L(L), R(R) {
        new_node();
    }
    void apply(int id, int x) {
        t[id].val = x;
        t[id].lazy = x;
    }
    void push(int id, int l, int r) {
        if (l != r && t[id].lazy != INT_MIN) {
            apply(t[id].l, t[id].lazy);
            apply(t[id].r, t[id].lazy);
            t[id].lazy = INT_MIN;
        }
    }
    void update(int u, int v, int x, int id, int l, int r) {
        if (v < l || r < u) return;
        if (u <= l && r <= v) {
            apply(id, x);
            return;
        }
        if (t[id].l == -1) t[id].l = new_node();
        if (t[id].r == -1) t[id].r = new_node();
        push(id, l, r);
        int mid = (l + r) >> 1;
        update(u, v, x, t[id].l, l, mid);
        update(u, v, x, t[id].r, mid + 1, r);
    }
    void update(int l, int r, int x) {
        update(l, r, x, 0, L, R);
    }
    int query(int p, int id, int l, int r) {
        if (l == r) return t[id].val;
        if (t[id].l == -1) t[id].l = new_node();
        if (t[id].r == -1) t[id].r = new_node();
        push(id, l, r);
        int mid = (l + r) >> 1;
        if (p <= mid) return query(p, t[id].l, l, mid);
        return query(p, t[id].r, mid + 1, r);
    }
    int query(int p) {
        return query(p, 0, L, R);
    }
};

void Nguyen_Tuong_Duy() {
    int n, m;
    cin >> n >> m;
    vector<rectangle> a(n);
    vector<event> e;
    for (int i = 0; i < n; ++i) {
        auto &[x1, y1, x2, y2] = a[i];
        cin >> x1 >> y1 >> x2 >> y2;
        e.push_back({x1, i, 1, 1});
        e.push_back({x2, i, 1, 0});
    }
    vector<point> b(m);
    for (int i = 0; i < m; ++i) {
        auto &[x, y, c] = b[i];
        cin >> x >> y >> c;
        e.push_back({x, i, 0, 0});
    }
    sort(e.begin(), e.end());
    set<line> se;
    map<line, line> prv;
    vector<vector<int>> adj(n), add_color(n);
    vector<bool> is_root(n, 1);
    lazy_dynamic_segment_tree t(1, 1'000'000'000);
    for (auto &[x, i, is_line, is_begin]: e) {
        if (is_line) {
            auto &[x1, y1, x2, y2] = a[i];
            line l = {y1, y2, i};
            if (!se.size()) {
                se.insert(l);
                t.update(l.y1, l.y2, i);
                continue;
            }
            if (x == x1) {
                auto it = se.lower_bound(l);
                if (it != se.begin()) {
                    --it;
                    if (y2 < it->y2) {
                        if (i > it->i) {
                            prv[l] = *it;
                            adj[it->i].emplace_back(l.i);
                            is_root[l.i] = 0;
                            se.erase(it);
                            se.insert(l);
                            t.update(l.y1, l.y2, i);
                        }
                    } else {
                        se.insert(l);
                        t.update(l.y1, l.y2, i);
                    }
                } else {
                    se.insert(l);
                    t.update(l.y1, l.y2, i);
                }
            } else {
                se.erase(l);
                auto it = prv.find(l);
                if (it != prv.end()) {
                    se.insert(it->second);
                    t.update(l.y1, l.y2, (it->second).i);
                    prv.erase(it);
                } else {
                    t.update(l.y1, l.y2, -1);
                }
            }
        } else {
            int j = t.query(b[i].y);
            if (j != -1) add_color[j].emplace_back(b[i].c);
        }
    }
    vector<int> ans(n);
    vector<set<int>> set_color(n);
    auto dfs = [&] (auto &&dfs, int u) -> void {
        for (auto &x: add_color[u]) set_color[u].insert(x);
        for (auto &v: adj[u]) {
            dfs(dfs, v);
            if (set_color[v].size() > set_color[u].size()) set_color[u].swap(set_color[v]);
            for (auto &x: set_color[v]) set_color[u].insert(x);
        }
        ans[u] = set_color[u].size();
    };
    for (int i = 0; i < n; ++i) if (is_root[i]) dfs(dfs, i);
    for (auto &i: ans) cout << i << '\n';
}

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