Submission #1241875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241875		felipe_massa	Plahte (COCI17_plahte)	C++20	160 / 160	223 ms	47436 KiB

plahte

#include<bits/stdc++.h>
#define int long long

using namespace std;
#define size(u) (int)(u).size()
#define pb push_back
#define fastio ios::sync_with_stdio(false); cin.tie(nullptr);
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

struct SegmentTree {
    int n;
    vector<int> t, lazy;
    SegmentTree(int n): n(n), t(4*n, -1), lazy(4*n, -2) {}
    void apply(int v, int val) {
        t[v] = val;
        lazy[v] = val;
    }
    void push(int v) {
        if (lazy[v] == -2) return;
        apply(2*v, lazy[v]);
        apply(2*v+1, lazy[v]);
        lazy[v] = -2;
    }
    void update(int v, int tl, int tr, int l, int r, int val) {
        if (l > tr || tl > r) {
            return;
        } else if (tl >= l && tr <= r) {
            apply(v, val);
        } else {
            push(v);
            int mid = (tl + tr) / 2;
            update(2*v, tl, mid, l, r, val);
            update(2*v+1, mid+1, tr, l, r, val); 
        }
    }
    void update(int l, int r, int val) {
        update(1, 0, n-1, l, r, val);
    }
    int query(int v, int tl, int tr, int pos) {
        if (tl == tr) {
            return t[v];
        } else {
            push(v);
            int mid = (tl + tr) / 2;
            if (pos <= mid) return query(2*v, tl, mid, pos);
            else return query(2*v+1, mid+1, tr, pos);
        }
    }
    int query(int pos) {
        return query(1, 0, n-1, pos);
    }
};

constexpr int N = 80004;
struct point {
    int x, y, id, prior;
    bool query = false;
    bool operator<(point o) {
        if (x < o.x) return true;
        if (x > o.x) return false;
        return prior < o.prior;
    }
};
ostream& operator<<(ostream& out, point p) {
    return out << p.x << ' ' << p.y << ' ' << p.id << ' ' << p.query;
}
struct sq {
    int l, r;
} squares[N];
int q[N], parent[N], ans[N];
set<int> smtol[N];
vector<int> ch[N];
vector<int> yvals;
bool open[N];
int getyval(int a) {
    return lower_bound(all(yvals), a) - yvals.begin();
}

void dfs(int cur) {
    for (auto u : ch[cur]) {
        dfs(u);
        if (size(smtol[u]) > size(smtol[cur])) smtol[u].swap(smtol[cur]);
        for (auto t : smtol[u]) smtol[cur].insert(t);
    }
    ans[cur] = size(smtol[cur]);
}

signed main() {
    fastio;
    int n, m; cin >> n >> m;
    vector<point> points;
    for (int i = 0; i < n; i++) {
        point p1, p2;
        cin >> p1.x >> p1.y >> p2.x >> p2.y;
        p1.id = p2.id = i;
        p1.prior = -2, p2.prior = 0;
        points.pb(p1); points.pb(p2);
        yvals.pb(p1.y); yvals.pb(p2.y);
        squares[i] = {p1.y, p2.y};
    }
    for (int i = 0; i < m; i++) {
        point p; cin >> p.x >> p.y;
        p.id = i, p.query = true;
        p.prior = -1;
        points.pb(p);
        yvals.pb(p.y);
        cin >> q[i];
    }
    sort(all(yvals));
    yvals.erase(unique(all(yvals)), yvals.end());
    for (auto & p : points) {
        p.y = getyval(p.y);
    }
    for (int i = 0; i < n; i++) {
        squares[i].l = getyval(squares[i].l);
        squares[i].r = getyval(squares[i].r);
    }
    sort(all(points));
    SegmentTree t(size(yvals));
    for (auto p : points) {
        if (p.query) {
            int par = t.query(p.y);
            if (par != -1)
                smtol[par].insert(q[p.id]);
        } else {
            if (open[p.id]) {
                t.update(squares[p.id].l, squares[p.id].r, parent[p.id]);
            } else {
                parent[p.id] = t.query(p.y);
                if (parent[p.id] != -1)
                    ch[parent[p.id]].pb(p.id);
                t.update(squares[p.id].l, squares[p.id].r, p.id);
                open[p.id] = true;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (parent[i] == -1) dfs(i);
    }
    for (int i = 0; i < n; i++) cout << ans[i] << '\n';
}

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