Submission #1127134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127134		MinhKien	Plahte (COCI17_plahte)	C++17	0 / 160	2097 ms	45788 KiB

plahte

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

using namespace std;

const int N = 1.6e5 + 1;

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

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

    SegmentTree() {
        fill_n(val, N << 2, 0);
        fill_n(lazy, N << 2, -1);
    }

    void change (int id, int VAL) {
        val[id] = lazy[id] = VAL;
    }

    void down(int id) {
        if (lazy[id] == -1) return;

        change(id << 1, lazy[id]);
        change(id << 1 | 1, lazy[id]);
        lazy[id] = -1;
    }

    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) {
            change(id, VAL);
            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);

        val[id] = max(val[id << 1], val[id << 1 | 1]);
    }

    int get(int l, int r, int A, int B, int id) {
        if (l > B || r < A) return -1;

        if (l >= A && r <= B) return val[id];

        int mid = (l + r) >> 1;
        down(id);
        return max(get(l, mid, A, B, id << 1), get(mid + 1, r, A, B, 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;
    }
} a[N];

bool cmp (rect x, rect y) {
    if (pair <int, int>(x.x1, x.y1) == pair <int, int>(y.x1, y.y1)) return pair <int, int>(x.x2, x.y2) < pair <int, int>(y.x2, y.y2);
    return pair <int, int>(x.x1, x.y1) < pair <int, int>(y.x1, y.y1);
}

unordered_map <int, int> ID;
int GetID(int p) {
    return ID[p];
}

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);
        s[z].clear();
    }

    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());
    
    for (int i = 0; i < Y.size(); ++i) {
        ID[Y[i]] = i + 1;
    }

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

    for (int i = 1; i <= n + m; ++i) {
        events.push_back(pair < pair <int, int>, int >(pair <int, int>(a[i].x1, a[i].y1), i));
        events.push_back(pair < pair <int, int>, int >(pair <int, int>(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].first < pair <int, int>(a[i].x1, a[i].y1)) {
            int cur = abs(events[j].second);
            if (events[j].second > 0) {
                seg.update(1, Y.size(), GetID(a[cur].y1), GetID(a[cur].y2), cur, 1);
            } else {
                int ph = par[cur];
                if (ph != 0) seg.update(1, Y.size(), GetID(a[ph].y1), GetID(a[ph].y2), ph, 1);
                else seg.update(1, Y.size(), GetID(a[cur].y1), GetID(a[cur].y2), 0, 1);
            }
            ++j;
        }

        int k = seg.get(1, Y.size(), GetID(a[i].y1), GetID(a[i].y2), 1);
        
        if (k > 0) {
            par[i] = k;
            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