제출 #1277361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277361		EliudGarcia	Plahte (COCI17_plahte)	C++17	160 / 160	244 ms	41640 KiB

plahte

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

#define ln '\n'
#define all(x) x.begin(), x.end()
#define forn(i, n) for(int i = 0; i < n; i++)
#define forab(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define sz(x) int(x.size())
#define rforn(i, n) for (int i = n-1; i >= 0; --i)
#define form(i, n, m, x) for (int i = n; i < m; i += x)
#define rform(i, n, m, x) for (int i = n; i >= m; i -= x)

#ifdef LOCAL
#include "debug.cpp"
#else
#define dbg(...)
#endif

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vll;

template<typename T>
struct STree {
    #define L(v) v << 1
    #define R(v) v << 1 | 1
    //L(v) = 2 * v
    //R(v) = 2 * v + 1

    int n;
    vector<T> st, lazy;
    T neutro = T(0);

    STree(int m) {
        n = m;
        st.resize(n * 4);
        lazy.resize(n * 4);
    }

    STree(vector<T> &a) {
        n = sz(a);
        st.resize(n * 4);
        lazy.resize(n * 4, -1);
        build(1, 0, n - 1, a);
    }

    T oper(T a, T b) {
        return max(a, b);
    }

    void build(int v, int tl, int tr, vector<T> &a) {
        if(tl == tr) {
            st[v] = a[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        build(L(v), tl, tm, a);
        build(R(v), tm + 1, tr, a);
        st[v] = oper(st[L(v)], st[R(v)]);
    }

    /* void push(int v, int tl, int tr) {
        if (!lazy[v]) return;
        st[v] += (tr - tl + 1) * lazy[v];
        if (tl != tr) {
            lazy[L(v)] += lazy[v];
            lazy[R(v)] += lazy[v];
        }
        lazy[v] = 0;
    } */


    void push(int v, int tl, int tr) {
        if (lazy[v] == -1) return;
        st[v] = lazy[v];
        if (tl != tr) {
            lazy[v * 2] = lazy[v];
            lazy[v * 2 + 1] = lazy[v];
        }
        lazy[v] = -1;
    }

    void upd(int v, int tl, int tr, int l, int r, T val) {
        push(v, tl, tr);
        if(tr < l || tl > r) return;
        if (tl >= l && tr <= r) {
            lazy[v] = val;
            push(v, tl, tr);
            return;
        }
        int tm = (tl + tr) / 2;
        upd(L(v), tl, tm, l, r, val);
        upd(R(v), tm + 1, tr, l, r, val);
        st[v] = oper(st[L(v)], st[R(v)]);
    }

    T query(int v, int tl, int tr, int l, int r) {
        push(v, tl, tr);
        if(tl > r || tr < l) return neutro;
        if (l <= tl && tr <= r) return st[v];
        int tm = (tl + tr) / 2;
        return oper(query(L(v), tl, tm, l, r), query(R(v), tm + 1, tr, l, r));
    }

    void upd(int l, int r, T val) {
        upd(1, 0, n - 1, l, r, val);
    }
    T query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};



struct event {
    int x, y, id, t;

    bool operator < (event &o) const {
        if(x == o.x) return t < o.t;
        return x < o.x;
    }
};

int n, m;
const int MAXN = 80005;
vector<array<int, 4>> rec(MAXN);
vector<array<int, 3>> pts(MAXN);
int parent[MAXN];
vi g[MAXN];
bool vis[MAXN];
int ans[MAXN];
set<int> dsu[MAXN];

vector<event> order;
vi compression;

int get_id(int x){
    return lower_bound(all(compression), x) - compression.begin();
}

set<int> dfs(int u, int p){
    if(vis[u]) return {};
    vis[u] = 1;
    set<int> a = dsu[u];

    for(int v: g[u]){
        if(!vis[v]){
            set<int> b = dfs(v, u);
            if(sz(a) < sz(b)) swap(a, b);

            for(int i: b){
                a.insert(i);
            }
        }
    }

    ans[u] = sz(a);
    return a;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        //freopen("out.txt", "w", stdout);
    #endif
    cin >> n >> m;

    forab(i, 1, n + 1){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        rec[i] = {x1, y1, x2, y2};

        order.pb({x1, y1, i, 0});
        order.pb({x2, y2, i, 2});


        compression.pb(y1);
        compression.pb(y2);
    }

    forab(i, 1, m + 1){
        int x, y, c;
        cin >> x >> y >> c;
        pts[i] = {x, y, c};

        order.pb({x, y, i, 1});

        compression.pb(y);
    }

    sort(all(order));


    sort(all(compression));
    compression.erase(unique(all(compression)), compression.end());

    vi aux(sz(compression) + 1, 0);

    forab(i, 1, n + 1) parent[i] = 0;

    STree<int> st(aux);

    for(auto [x, y, i, type] : order){
        if(type == 0){
            //rectangulo inicio
            auto [x1, y1, x2, y2] = rec[i];

            int l = get_id(y1);
            int r = get_id(y2);

            parent[i] = st.query(l, r);
            st.upd(l, r, i);

        }else if(type == 1){
            //punto
            int idx = get_id(y);
            int p = st.query(idx, idx);
            dsu[p].insert(pts[i][2]);

        }else{
            //rectangulo fin
            auto [x1, y1, x2, y2] = rec[i];

            int l = get_id(y1);
            int r = get_id(y2);

            st.upd(l, r, parent[i]);
        }
    }

    forab(i, 1, n + 1){
        g[parent[i]].pb(i);
        g[i].pb(parent[i]);
    }

    dfs(0, 0);

    forab(i, 1, n + 1) {
        cout << ans[i] << ln;
    }

    return 0;
}


//https://oj.uz/problem/view/COCI17_plahte

// Dan N rectangulos que NO se intersectan ni se tocan
// pero si pueden haber rectangulos contenidos en otros
// los rectangulos representan hojas de papel

// luego M bolas de colores son disparadas 
// en coordenadas unicas (x, y, color)
// algunas caen dentro de rectangulos y otras por fuera

//cuando una bola cae en una hoja de papel, queda marcada 
//en las hojas que estan debajo (contenidas)

// para cada hoja (rectangulo) decir cuantos colores diferentes
// contiene

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