Submission #1128590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128590		TrendBattles	Plahte (COCI17_plahte)	C++17	160 / 160	373 ms	75028 KiB

plahte

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

#define INFILE "present.inp"
#define OUTFILE "present.out"

struct Rectangle {
    int a, b, c, d;
    Rectangle(int _a = 0, int _b = 0, int _c = 0, int _d = 0):
        a(_a), b(_b), c(_c), d(_d) {}
};


struct Compressed_Data {
    vector <int> comp_value;

    Compressed_Data() {}

    void add(int x) {
        comp_value.push_back(x);
    }    
    void build() {
        sort(comp_value.begin(), comp_value.end());
        comp_value.erase(unique(comp_value.begin(), comp_value.end()), comp_value.end());
    }

    int get_pos(int x) {
        int id = lower_bound(comp_value.begin(), comp_value.end(), x) - comp_value.begin();

        return id >= (int) comp_value.size() or comp_value[id] != x ? -1 : id;
    }

    int get_size() const {
        return (int) comp_value.size();
    }

    void debug() {
        cerr << "DEBUG\n";
        for (int x : comp_value) cerr << x << ' ';
        cerr << '\n';
    }
};

const int inf_32 = 0x3f3f3f3f;
struct SegmentTree {
    vector <vector <int>> node;
    int N;

    SegmentTree(int N): N(N), node(N << 2) {

    }

    void update_range(int v, int tl, int tr, int l, int r, int id) {
        if (l > r) return;
        if (l == tl and r == tr) {
            node[v].push_back(id);
            return;
        }

        int tm = (tl + tr) >> 1;
        update_range(v << 1, tl, tm, l, min(r, tm), id);
        update_range(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, id);
    }

    void update_range(int l, int r, int id) {
        update_range(1, 0, N - 1, l, r, id);
    }

    void remove(int v, int tl, int tr, int l, int r) {
        if (l > r) return;
        if (l == tl and r == tr) {
            node[v].pop_back();
            return;
        }

        int tm = (tl + tr) >> 1;
        remove(v << 1, tl, tm, l, min(r, tm));
        remove(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r);
    }

    void remove(int l, int r) {
        remove(1, 0, N - 1, l, r);
    }

    int get_value(int v, int tl, int tr, int pos) {
        int A = node[v].empty() ? -1 : node[v].back();
        if (tl == tr) return A;

        int tm = (tl + tr) >> 1;
        int B = -1;

        if (pos <= tm) {
            B = get_value(v << 1, tl, tm, pos);
        } else {
            B = get_value(v << 1 | 1, tm + 1, tr, pos);
        }

        if (B != -1) A = B;
        return A;
    }
    int get_value(int pos) {
        return get_value(1, 0, N - 1, pos);
    }
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen(INFILE, "r")) {
        freopen(INFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }

    int N, Q; cin >> N >> Q;
    
    vector <Rectangle> rect(N);

    Compressed_Data X_pos, Y_pos;
    for (Rectangle& R : rect) {
        cin >> R.a >> R.b >> R.c >> R.d;
        X_pos.add(R.a); X_pos.add(R.c);
        Y_pos.add(R.b); Y_pos.add(R.d);
    }

    vector <int> present_X(Q), present_Y(Q), color(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> present_X[i] >> present_Y[i] >> color[i];
        X_pos.add(present_X[i]);
        Y_pos.add(present_Y[i]);
    }

    X_pos.build(); Y_pos.build();
    
    
    for (Rectangle& R : rect) {
        R.a = X_pos.get_pos(R.a); R.c = X_pos.get_pos(R.c);
        R.b = Y_pos.get_pos(R.b); R.d = Y_pos.get_pos(R.d);
    }
    for (int i = 0; i < Q; ++i) {
        present_X[i] = X_pos.get_pos(present_X[i]);
        present_Y[i] = Y_pos.get_pos(present_Y[i]);
    }

    const int M = X_pos.get_size();
    vector <vector <int>> open_line(M), presents(M), close_line(M);

    for (int i = 0; i < N; ++i) {
        Rectangle& R = rect[i];
        open_line[R.a].push_back(i);
        close_line[R.c].push_back(i);
    }
    for (int i = 0; i < Q; ++i) {
        presents[present_X[i]].push_back(i);
    }
    

    vector <set <int>> color_set(N);
    vector <vector <int>> graph(N);

    SegmentTree tree(Y_pos.get_size());

    for (int _ = 0; _ < M; ++_) {
        for (int x : open_line[_]) {
            Rectangle& R = rect[x];

            int p = tree.get_value(R.b);
            if (p >= 0 and p < N) {
                graph[p].push_back(x);
            }

            tree.update_range(R.b, R.d, x);
        }

        for (int id : presents[_]) {
            int p = tree.get_value(present_Y[id]);

            //cerr << "PRESENT " << id << ": " << p << '\n';

            if (p >= 0 and p < N) {
                color_set[p].insert(color[id]);
            }
        }

        for (int x : close_line[_]) {
            Rectangle& R = rect[x];

            tree.remove(R.b, R.d);
        }
    }

    vector <int> visited(N), finale(N);
    auto DFS = [&] (auto DFS, int u) -> void {
        if (visited[u]) return;
        visited[u] = true;

        for (int v : graph[u]) {
            DFS(DFS, v);

            if ((int) color_set[u].size() < color_set[v].size()) color_set[u].swap(color_set[v]);

            for (int x : color_set[v]) color_set[u].insert(x);
            color_set[v].clear();
        }

        finale[u] = (int) color_set[u].size();
    };
    for (int i = 0; i < N; ++i) {
        DFS(DFS, i);

        cout << finale[i] << '\n';
    }
    return 0;
}

/*

10 10
18 20 27 25 
33 29 34 30 
41 39 47 50 
7 5 17 19 
31 26 32 28 
8 8 16 17 
43 48 46 49 
9 11 11 15 
20 22 22 24 
36 32 38 36 
32 28 6
17 8 9
18 20 2
16 8 10
35 30 7
48 32 8
27 28 7
16 8 8
50 28 9
41 50 4
*/

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
plahte.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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