oj.uz

Submission #651953

# Submission time Handle Problem Language Result Execution time Memory
651953 2022-10-20T17:36:23 Z bebra Plahte (COCI17_plahte) C++17
160 / 160
 554 ms 92368 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;


struct Event {
    int idx;
    int y1;
    int y2;

    Event(int _idx = 0, int _y1 = 0, int _y2 = 0)
        : idx(_idx), y1(_y1), y2(_y2) {}
};

struct Point {
    int y;
    int color;
    Point(int _y = 0, int _color = 0)
        : y(_y), color(_color) {}
};


template<typename T>
unordered_map<T, int> compress(vector<T>& a) {
    sort(a.begin(), a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
    unordered_map<int, int> data;
    for (int i = 0; i < (int)a.size(); ++i) {
        data[a[i]] = i;
    }
    return data;
}


struct SegmentTree {
    static const int NO_OP = -1e9;

    struct Node {
        int value;
        Node(int _value = NO_OP) : value(_value) {}
    };

    vector<Node> tree;
    int size;

    SegmentTree(int n) {
        size = 1 << (__lg(n) + 1);
        tree.resize(2 * size - 1);
    }

    void push(int l, int r, int v) {
        if (l == r - 1 || tree[v].value == NO_OP) return;
        tree[2 * v + 1].value = tree[v].value;
        tree[2 * v + 2].value = tree[v].value;
        tree[v].value = NO_OP;
    }

    void update(int lq, int rq, int value) {
        update(0, size, 0, lq, rq + 1, value);
    }

    void update(int l, int r, int v, int lq, int rq, int value) {
        push(l, r, v);
        if (lq <= l && r <= rq) {
            tree[v].value = value;
            return;
        } else if (l >= rq || r <= lq) {
            return;
        }
        int m = (l + r) / 2;
        update(l, m, 2 * v + 1, lq, rq, value);
        update(m, r, 2 * v + 2, lq, rq, value);
    }

    int query(int pos) {
        return query(0, size, 0, pos);
    }

    int query(int l, int r, int v, int pos) {
        push(l, r, v);
        if (l == r - 1) {
            return tree[v].value;
        }
        int m = (l + r) / 2;
        if (pos < m) {
            return query(l, m, 2 * v + 1, pos);
        } else {
            return query(m, r, 2 * v + 2, pos);
        }
    }
};

const int MAX_N = 3e5 + 5;
const int MAX_SUM = 3e5 + 5;
vector<Event> rect_starts[MAX_SUM];
vector<Event> rect_ends[MAX_SUM];
vector<Point> point_events[MAX_SUM];

int ans[MAX_N];
int parent[MAX_N];
vector<int> g[MAX_N];
unordered_set<int> colors[MAX_N];

void dfs(int v) {
    for (int u : g[v]) {
        dfs(u);
        if (colors[u].size() > colors[v].size()) {
            swap(colors[u], colors[v]);
        }
        for (auto c : colors[u]) {
            colors[v].insert(c);
        }
    }
    ans[v] = colors[v].size();
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int, int>> rects(n);
    vector<int> x_coords, y_coords;
    x_coords.reserve(n + m);
    y_coords.reserve(n + m);
    for (auto& [x1, y1, x2, y2] : rects) {
        cin >> x1 >> y1;
        cin >> x2 >> y2;
        x_coords.push_back(x1);
        x_coords.push_back(x2);
        y_coords.push_back(y1);
        y_coords.push_back(y2);
    }
    vector<tuple<int, int, int>> points(m);
    for (auto& [x, y, color] : points) {
        cin >> x >> y;
        cin >> color;
        x_coords.push_back(x);
        y_coords.push_back(y);
    }
    unordered_map<int, int> x_map, y_map;
    x_map = compress(x_coords);
    y_map = compress(y_coords);
    for (int i = 0; i < n; ++i) {
        auto [x1, y1, x2, y2] = rects[i];
        x1 = x_map[x1];
        x2 = x_map[x2];
        y1 = y_map[y1];
        y2 = y_map[y2];
        rect_starts[x1].emplace_back(i, y1, y2);
        rect_ends[x2].emplace_back(i, y1, y2);
    }
    for (auto [x, y, color] : points) {
        x = x_map[x];
        y = y_map[y];
        point_events[x].emplace_back(y, color);
    }
    SegmentTree segtree(y_map.size());
    segtree.update(0, (int)y_map.size() - 1, -1);
    for (auto x = 0; x < (int)x_coords.size(); ++x) {
        for (const auto& [idx, y1, y2] : rect_starts[x]) {
            parent[idx] = segtree.query(y1);
            if (parent[idx] != -1) {
                g[parent[idx]].push_back(idx);
            }
            segtree.update(y1, y2, idx);
        }
        for (const auto [y, color] : point_events[x]) {
            auto v = segtree.query(y);
            if (v != -1) {
                colors[v].insert(color);
            }
        }
        for (const auto& [idx, y1, y2] : rect_ends[x]) {
            segtree.update(y1, y2, parent[idx]);
        }
    }
    for (int v = 0; v < n; ++v) {
        if (parent[v] == -1) {
            dfs(v);
        }
    }
    for (int v = 0; v < n; ++v) {
        cout << ans[v] << '\n';
    }
    return 0;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 58692 KB Output is correct
2 Correct 141 ms 60736 KB Output is correct
3 Correct 26 ms 44884 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 62988 KB Output is correct
2 Correct 161 ms 62408 KB Output is correct
3 Correct 26 ms 44956 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 75056 KB Output is correct
2 Correct 268 ms 72832 KB Output is correct
3 Correct 30 ms 44884 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 92248 KB Output is correct
2 Correct 554 ms 92368 KB Output is correct
3 Correct 30 ms 44876 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 90708 KB Output is correct
2 Correct 481 ms 89912 KB Output is correct
3 Correct 27 ms 44884 KB Output is correct