Submission #1184788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184788		nh0902	Plahte (COCI17_plahte)	C++20	0 / 160	2095 ms	8912 KiB

plahte

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;

const int N = 2e5;

struct Hcn {
    int a, b, c, d;
    int id, color;
};

bool cmp(Hcn h1, Hcn h2) {
    if (h1.c == h2.c) return h1.c - h1.a < h2.c - h2.a;
    return h1.c < h2.c;

}

int n, m;

Hcn h[N];

int pa[N];

vector<int> child[N];

struct cmp_Hcn {
    bool operator()(int i, int j) const {
        if (h[i].b == h[j].b) return i < j;
        return h[i].b < h[j].b;
    }
};

void prep() {
    sort(h + 1, h + 1 + n + m, cmp);

    int cur = 1;
    set<int, cmp_Hcn> store;
    for (int i = 1; i <= n + m; i ++) {

        //cout << i << " : " << h[i].a << " " << h[i].b << " " << h[i].c << " " << h[i].d << "\n";

        while (cur <= n + m && h[cur].c <= h[i].a) {
            store.erase(cur);
            cur ++;
        }

        store.insert(i);

        auto it = store.upper_bound(i);

        vector<int> need_erase;

        while (it != store.end()) {
            int p = *it;
            //cout << i << " : " << p << "\n";
            if (h[p].a >= h[i].a && h[p].c <= h[i].c && h[p].b >= h[i].b && h[p].d <= h[i].d) {
                need_erase.push_back(p);
                pa[p] = i;
                ++it;
            } else {
                ++it;
            }
        }

        for (int p : need_erase) store.erase(p);

        store.insert(i);
    }

    for (int i = 1; i <= n + m; i ++) {
        child[pa[i]].push_back(i);
    }
}

void prep2() {
    for (int i = 1; i <= m + n; i ++) {
        for (int j = 1; j <= m + n; j ++) {
            if (i == j) continue;
            if (h[i].a >= h[j].a && h[i].c <= h[j].c && h[i].b >= h[j].b && h[i].d <= h[j].d) {
                pa[i] = j;

                //  cout << i << " " << j << "\n";

            }
        }
    }

    for (int i = 1; i <= n + m; i ++) {
        child[pa[i]].push_back(i);
    }
}

int sz[N];

int ans[N];

int cur_ans;

int cur_cnt[N];

void dfs(int u) {
    sz[u] = 1;
    for (int v : child[u]) {
        dfs(v);
        sz[u] += sz[v];
    }
}

void decre(int u) {

    cur_cnt[h[u].color] --;
    if (cur_cnt[h[u].color] == 0) cur_ans --;

    for (int v : child[u]) {
        decre(v);
    }
}

void incre(int u) {

    cur_cnt[h[u].color] ++;
    if (cur_cnt[h[u].color] == 1) cur_ans ++;

    for (int v : child[u]) {
        incre(v);
    }
}

void DFS(int u) {

    if (child[u].size() == 0) {
        cur_cnt[h[u].color] ++;
        if (cur_cnt[h[u].color] == 1) cur_ans ++;
        return;
    }

    int b = 0;
    for (int v : child[u]) {
        if (b == 0 || sz[v] > sz[b]) b = v;
    }

    for (int v : child[u]) if (v != b) {
        DFS(v);
        decre(v);
    }

    DFS(b);

    for (int v : child[u]) if (v != b) {
        incre(v);
    }

    //cout << u << " " << cur_ans << " " << cur_cnt[0] << " " << cur_cnt[1] << " " << cur_cnt[2] << " " << cur_cnt[3] << "\n";

    ans[h[u].id] = cur_ans - (cur_cnt[0] > 0);

    cur_cnt[h[u].color] ++;
    if (cur_cnt[h[u].color] == 1) cur_ans ++;

}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        cin >> h[i].a >> h[i].b >> h[i].c >> h[i].d;
        h[i].id = i;
    }

    for (int i = 1; i <= m; i ++) {
        cin >> h[i + n].a >> h[i + n].b >> h[i + n].color;
        h[i + n].c = h[i + n].a;
        h[i + n].d = h[i + n].b;
    }

    //prep();

    prep2();

    //for (int i = 1; i <= m + n; i ++) cout << i << " " << pa[i] << "\n";

    //set<int, cmp_Hcn> s;
    //for (int i = 1; i <= m + n; i ++) s.insert(i);
    //for (auto it = s.begin(); it != s.end(); ++it) cout << *it << " ";

    dfs(0);
    DFS(0);

    for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
}

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