Submission #1279419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279419		MinhKien	Plahte (COCI17_plahte)	C++17	0 / 160	268 ms	40044 KiB

plahte

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

using namespace std;

#define ii pair <int, int>
#define iii pair <ii, int>
const int N = 1.6e5 + 10;

int n, m;
vector <int> v;
bool IsRoot[N];
vector <iii> events;
vector <int> g[N];
int par[N], ans[N];

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

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

        id = i;
    }

    bool operator < (const rec &o) const {
        if (ii(x1, y1) == ii(o.x1, o.y1)) return ii(x2, y2) < ii(o.x2, y2);
        return ii(x1, y1) < ii(o.x1, o.y1);
    }
} a[N];

struct SEG {
    int val[N * 6], lazy[N * 6];

    SEG () {
        memset(val, 0, sizeof val);
        memset(lazy, -1, sizeof lazy);
    }

    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 L, int R, int VAL, int id) {
        if (l > R || r < L) return;

        if (l >= L && r <= R) {
            change(id, VAL);
            return;
        }

        int mid = (l + r) >> 1;
        down(id);
        update(l, mid, L, R, VAL, id << 1);
        update(mid + 1, r, L, R, VAL, id << 1 | 1);

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

    int get(int l, int r, int L, int R, int id) {
        if (l > R  || r < L) return 0;

        if (l >= L && r <= R) return val[id];

        int mid = (l + r) >> 1;
        if (l == 1 && r == 2) {

        }
        down(id);
        return max(get(l, mid, L, R, id << 1), get(mid + 1, r, L, R, id << 1 | 1));
    }
} seg;

bool cmp (const iii &X, const iii &Y) {
    if (X.first == Y.first) {
        return X.second < Y.second;
    }
    return X.first < Y.first;
}

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

set <int> col[N];
void DFS(int s) {
    if (a[s].k != -1) {
        col[s].insert(a[s].k);
    }

    for (int z: g[s]) {
        DFS(z);
        if (col[z].size() > col[s].size()) swap(col[s], col[z]);
        for (int kk: col[z]) {
            col[s].insert(kk);
        }
    }

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

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

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

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

    for (int i = 1; i <= n + m; ++i) {
        a[i].y1 = ID(a[i].y1);
        a[i].y2 = ID(a[i].y2);
        if (a[i].id <= n) {
            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(), cmp);

    int j = 0;
    for (int i = 1; i <= n + m; ++i) {
        while (j < (int)events.size() && events[j].first < ii(a[i].x1, a[i].y1)) {
            int cur = events[j].second;
            if (events[j].second > 0) {
                seg.update(1, v.size(), a[cur].y1, a[cur].y2, cur, 1);
            } else {
                cur = -cur;
                int ph = par[cur];
                if (ph != 0) seg.update(1, v.size(), a[ph].y1, a[ph].y2, ph, 1);
                else seg.update(1, v.size(), a[cur].y1, a[cur].y2, 0, 1);
            }
            ++j;
        }

        int k = seg.get(1, v.size(), a[i].y1, a[i].y2, 1);

        if (k > 0) {
            par[i] = k;
            g[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