Submission #1128574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128574		TrendBattles	Plahte (COCI17_plahte)	C++17	0 / 160	338 ms	49464 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 <int> node, lazy;
    int N;

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

    }

    void Apply(int v, int id);
    void Push(int v);

    void update_range(int v, int tl, int tr, int l, int r, int id);
    void update_range(int l, int r, int id);
    
    int get_value(int 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);
    }
    

    SegmentTree tree(Y_pos.get_size());
    vector <set <int>> color_set(N);
    vector <vector <int>> graph(N);

    for (int _ = 0; _ < M; ++_) {
        //cerr << "NOW: " << X_pos.comp_value[_] << '\n';
        for (int x : open_line[_]) {
            Rectangle& R = rect[x];
            //cerr << "OPEN " << x << '\n';

            int p = tree.get_value(R.c);

            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 << "CHECK " << id << ' ' << p << '\n';

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

        for (int x : close_line[_]) {
            //cerr << "CLOSE " << x << '\n';
            Rectangle& R = rect[x];

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

    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;
}

void SegmentTree::Apply(int v, int id) {
    node[v] = lazy[v] = id;
}

void SegmentTree::Push(int v) {
    if (lazy[v] >= inf_32 / 2) return;

    for (int child : {v << 1, v << 1 | 1}) {
        Apply(child, lazy[v]);
    }

    lazy[v] = inf_32;
}
void SegmentTree::update_range(int v, int tl, int tr, int l, int r, int id) {
    if (l > r) return;
    if (l == tl and r == tr) {
        Apply(v, id);
        return;
    }

    int tm = (tl + tr) >> 1;
    Push(v);
    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 SegmentTree::update_range(int l, int r, int id) {
    update_range(1, 0, N - 1, l, r, id);
}

int SegmentTree::get_value(int pos) {
    int v = 1, l = 0, r = N - 1;
    while (l < r) {
        Push(v);

        int mid = (l + r) >> 1;
        if (pos <= mid) {
            v <<= 1; r = mid;
        } else {
            v = v << 1 | 1; l = mid + 1;
        }
    }

    return node[v];
}

/*
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:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
plahte.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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