Submission #1127032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127032		MinhKien	Plahte (COCI17_plahte)	C++20	0 / 160	625 ms	589824 KiB

plahte

#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <set>

#define ii pair <int, int>
#define iii pair <ii, int>
#define fi first
#define se second
using namespace std;

const int N = 2e5 + 10;

int n, m, ans[N];
set <int> s[N];
vector <int> v[N], Y;
vector <iii> events;
bool IsRoot[N];

struct SegmentTree {
    vector <int> val[N << 2];
    vector <int> lazy[N << 2];

    void down(int id) {
        if (lazy[id].size() == 0) return;

        for (int z: lazy[id]) {
            if (z < 0) {
                val[id << 1].pop_back();
                val[id << 1 | 1].pop_back();
            } else {
                val[id << 1].push_back(z);
                val[id << 1 | 1].push_back(z);
            }
            lazy[id << 1].push_back(z);
            lazy[id << 1 | 1].push_back(z);
        }
        lazy[id].clear();
    }

    void update(int l, int r, int A, int b, int VAL, int id) {
        if (l > b || r < A) return;

        if (l >= A && r <= b) {
            if (VAL > 0) {
                val[id].push_back(VAL);
                lazy[id].push_back(VAL);
            } else {
                if (lazy[id].empty()) lazy->push_back(VAL);
                else lazy[id].pop_back();
            }
            return;
        }

        int mid = (l + r) >> 1;
        down(id);
        update(l, mid, A, b, VAL, id << 1);
        update(mid + 1, r, A, b, VAL, id << 1 | 1);
    }

    int get(int l, int r, int A, int id) {
        if (l == r) {
            if (val[id].empty()) return 0;
            return val[id].back();
        }

        int mid = (l + r) >> 1;
        down(id);
        if (A <= mid) return get(l, mid, A, id << 1);
        return get(mid + 1, r, A, id << 1 | 1);
    }
} seg;

struct rect {
    int x1, y1, x2, y2;
    int id, k;

    void input(int i) {
        if (i <= n) {
            cin >> x1 >> y1 >> x2 >> y2;
            k = -1;
        } else {
            cin >> x1 >> y1 >> k;
            x2 = x1;
            y2 = y1;
        }

        Y.push_back(y1);
        Y.push_back(y2);

        id = i;
    }

    void output() {
        cout << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
    }

    bool in (int l, int r, int u) {
        return u >= l && u <= r;
    }

    bool rect_in (rect o) {
        return in(x1, x2, o.x1) && in(x1, x2, o.x2) && in(y1, y2, o.y1) && in(y1, y2, o.y2);
    }
} a[N];

bool cmp (rect x, rect y) {
    if (x.rect_in(y)) return true;
    if (y.rect_in(x)) return false;
    return ii(x.x1, x.y1) < ii(y.x1, y.y2);
}

int GetID(int p) {
    return lower_bound(Y.begin(), Y.end(), p) - Y.begin() + 1;
}

void DFS(int u) {
    if (a[u].k != -1) {
        s[u].insert(a[u].k);
    }

    for (int z: v[u]) {
        DFS(z);
        if (s[u].size() > s[z].size()) s[u].swap(s[z]);
        for (int j: s[z]) s[u].insert(j);
    }

    ans[a[u].id] = s[u].size();
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i <= n + m; ++i) {
        a[i].input(i);
        IsRoot[i] = true;
    }

    sort(Y.begin(), Y.end());
    Y.erase(unique(Y.begin(), Y.end()), Y.end());

    sort(a + 1, a + n + m + 1, cmp);

    for (int i = 1; i <= n + m; ++i) {
        events.push_back(iii(ii(a[i].x1, a[i].y1), i));
        events.push_back(iii(ii(a[i].x2, a[i].y2), -i));
    }
    sort(events.begin(), events.end());

    int j = 0;
    for (int i = 1; i <= n + m; ++i) {
        while (j < events.size() && events[j].fi < ii(a[i].x1, a[i].y1)) {
            seg.update(1, Y.size(), GetID(a[abs(events[j].se)].y1), GetID(a[abs(events[j].se)].y2), events[j].se, 1);
            ++j;
        }

        int k = seg.get(1, Y.size(), GetID(a[i].y1), 1);
        if (k != 0) {
            v[k].push_back(i);
            IsRoot[i] = false;
        }
    }

    for (int i = 1; i <= n + m; ++i) {
        if (IsRoot[i]) {
            DFS(i);
        }
    }

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

    return 0;
}

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