Submission #1237089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237089		EliudGarcia	Plahte (COCI17_plahte)	C++17	0 / 160	242 ms	51404 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>
void print(T *a, int l, int r){
    cout << "===> [";
    for(int i = l; i < r; i++){
        if(i == r - 1) cout << (a[i]) << "]\n";
        else cout << a[i] << ", ";
    }
}

template<typename T>
struct STree {
    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);
        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(v * 2, tl, tm, a);
        build(v * 2 + 1, tm + 1, tr, a);
        st[v] = oper(st[v * 2], st[v * 2 + 1]);
    }

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

    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(v * 2, tl, tm, l, r, val);
        upd(v * 2 + 1, tm + 1, tr, l, r, val);
        st[v] = oper(st[v * 2], st[v * 2 + 1]);
    }

    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(v * 2, tl, tm, l, r), query(v * 2 + 1, 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, is_rec, is_end;
    bool operator <(event &o) const {
        if(x == o.x){
            if(is_rec && !is_end){
                return is_rec > o.is_end;
            }else{
                return is_rec < o.is_end;
            }
        }
        return x < o.x;
    }
};

int n, m;
const int MAXN = 80005;
int color[MAXN];
int parent[MAXN];
set<int> cc[MAXN];
map<int, int> sack[MAXN];

vi compresion;
vector<event> barrido;

vi g[MAXN];
int sub_sz[MAXN];
int ans[MAXN];
bool vis[MAXN];

void dfs1(int u, int p){
    if(vis[u]) return;
    vis[u] = 1;
    sub_sz[u] = 1;
    for(int v: g[u]){
        if(v == p) continue;
        dfs1(v, u);
        sub_sz[u] += sub_sz[v];
    }
}

void dfs2(int u, int p){
    if(vis[u]) return;
    int big = -1, mx = -1;
    vis[u] = 1;
    for(int v: g[u]){
        if(v == p) continue;
        if(sub_sz[v] > mx){
            mx = sub_sz[v];
            big = v;
        }
    }

    for(int v: g[u]){
        if(v == p || v == big) continue;
        dfs2(v, u);
    }

    if(big != -1){
        dfs2(big, u);
        swap(sack[u], sack[big]);
        //ahora u tiene el set mas grande
    }

    //small to large
    for(int v: g[u]){
        if(v == p || v == big) continue;
        for(auto [c, occ] : sack[v]){
            sack[u][c] += occ;
        }
    }

    for(int i: cc[u]){
        sack[u][i]++;//incluir u
    }
    //ans queries
    ans[u] = sz(sack[u]);
}


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;
    vector<array<int, 2>> rect(n + 1);

    forn(i, n){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        barrido.pb({x1, y1, i + 1, 1, 0}); //inicio
        barrido.pb({x2, y2, i + 1, 1, 1}); //fin

        int alto = abs(y2 - y1);
        int ancho = abs(x2 - x1);
        rect[i + 1] = {alto, ancho};
    }

    forn(i, m){
        int x, y, c;
        cin >> x >> y >> c;
        barrido.pb({x, y, i + 1, 0, 0});
        color[i + 1] = c;
    }

    // sweep line
    sort(all(barrido));

    forn(i, sz(barrido)){
        int x = barrido[i].x;
        int y = barrido[i].y;
        compresion.pb(x);
        compresion.pb(y);
    }

    //compresion de coordenadas
    sort(all(compresion));
    compresion.erase(unique(all(compresion)), compresion.end());

    int tam = sz(compresion) + 5;
    vi aux(tam, n + 2);
    STree<int> st(aux);


    for(auto [x, y, id, is_rec, is_end] : barrido){
        int ny = lower_bound(all(compresion), y) - compresion.begin();

        //rectangulo
        if(is_rec){
            //dbg(x, y, "r");
            if(!is_end){
                int l = ny;
                int r = ny + rect[id][0];

                //rango = [y1 + altura, y1]
                //settear el rango a i
                parent[id] = st.query(l, r); //-----------
                st.upd(l, r, id);
            }else{
                int r = ny;
                int l = ny - rect[id][0];

                int p = parent[id];
                st.upd(l, r, p);
            }
        }else if(!is_rec){
            //punto
            //dbg(x, y, "P");
            int contenido = st.query(ny, ny);
            //dbg(contenido);
            cc[contenido].insert(color[id]);
        }
    }

    int root = 0;
    forab(i, 1, n + 1){
        if(parent[i] == n + 2){
            root = i;
            continue;
        }
        g[parent[i]].pb(i);
        g[i].pb(parent[i]);
    }

    forab(i, 1, n + 1){
        if(!vis[i]) dfs1(i, 0);
    }
    fill(vis + 1, vis + n + 1, 0);
    forab(i, 1, n + 1){
        if(!vis[i]) dfs2(i, 0);
    }


    /*dbg(cc[1]);
    dbg(cc[2]);
    dbg(cc[3]);
    */
    forab(i, 1, n + 1){
        cout << ans[i] << ln;
    }


    return 0;
}

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