Submission #1208271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208271		urejgi	Plahte (COCI17_plahte)	C++17	160 / 160	284 ms	85652 KiB

plahte

#pragma GCC optimize("O3,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,tune=native,fma")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 5e5;

struct ST{
    int n;
    vector<int> tr, lz;
    void init(int _n){
        n = _n;
        tr.resize(n<<2|1);
        lz.assign(n<<2|1, 1);
    }
    void push(int t){
        if (lz[t]) return;
        tr[t<<1] = tr[t];
        tr[t<<1|1] = tr[t];
        lz[t<<1] = lz[t<<1|1] = 0;
        lz[t] = 1;
    }
    void add(int t, int l, int r, int ql, int qr, int x){
        if (r < ql || l > qr) return;
        if (ql <= l&& r <= qr){
            tr[t] = x;
            lz[t] = 0;
            return;
        }
        push(t);
        int m = (l + r) >> 1;
        add(t<<1, l, m, ql, qr, x);
        add(t<<1|1, m + 1, r, ql, qr, x);
    }
    int get(int t, int l, int r, int i){
        if (l == r) return tr[t];
        push(t);
        int m = (l + r) >> 1;
        if (i <= m) return get(t<<1, l, m, i);
        return get(t<<1|1, m + 1, r, i);
    }
    void add(int l, int r, int x){ add(1, 1, n, l, r, x); }
    int get(int i){ return get(1, 1, n, i); }
} tree;

struct event{
    int a, b, c, i;
    event(int _a = 0, int _b = 0, int _c = 0, int _d = 0):a(_a), b(_b), c(_c), i(_d){}
    bool operator<(const event&b) const{
        if (a == b.a){
            if (i < 0) return 0;
            if (b.i < 0) return 1;
            return c < b.c;
        }
        return a < b.a;
    }
};

struct S{
    int a, b, c, d;
    S(int _a = 0, int _b = 0, int _c = 0, int _d = 0):a(_a), b(_b), c(_c), d(_d){}
};

struct ball{
    int a, b, c;
    ball(int _a = 0, int _b = 0, int _c = 0):a(_a), b(_b), c(_c){}
};

int n, m, pa[N], pb[N], ans[N];
S a[N];
ball b[N];
set<int> col[N];
vector<event> evs;
vector<int> zip, g[N];

inline int pos(int x){
    return upper_bound(zip.begin(), zip.end(), x) - zip.begin();
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    zip.reserve(4*n + 2*m + 100);
    for(int i = 1; i <= n; ++i){
        cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
        zip.push_back(a[i].a);
        zip.push_back(a[i].b);
        zip.push_back(a[i].c);
        zip.push_back(a[i].d);
    }
    for(int i = 1; i <= m; ++i){
        cin >> b[i].a >> b[i].b >> b[i].c;
        zip.push_back(b[i].a);
        zip.push_back(b[i].b);
    }
    sort(zip.begin(), zip.end());
    zip.erase(unique(zip.begin(), zip.end()), zip.end());
    tree.init(zip.size());
    for(int i = 1; i <= n; ++i){
        a[i].a = pos(a[i].a);
        a[i].b = pos(a[i].b);
        a[i].c = pos(a[i].c);
        a[i].d = pos(a[i].d);
    }
    for(int i = 1; i <= m; ++i){
        b[i].a = pos(b[i].a);
        b[i].b = pos(b[i].b);
    }
    for(int i = 1; i <= n; ++i){
        evs.emplace_back(a[i].a, a[i].b, a[i].d, i);
        evs.emplace_back(a[i].c, a[i].b, a[i].d, -i);
    }
    for(int i = 1; i <= m; ++i){
        evs.emplace_back(b[i].a, b[i].b, N, i);
    }
    sort(evs.begin(), evs.end());
    for(auto&tmp:evs){
        if (tmp.c == N){
            pb[tmp.i] = tree.get(tmp.b);
            col[pb[tmp.i]].insert(b[tmp.i].c);
            continue;
        }
        if (tmp.i < 0){
            tree.add(tmp.b, tmp.c, pa[-tmp.i]);
        } else{
            pa[tmp.i] = tree.get(tmp.b); 
            g[pa[tmp.i]].push_back(tmp.i);
            tree.add(tmp.b, tmp.c, tmp.i);
        }
    }
    function<void(int, int)> dfs = [&](int v, int pv) -> void{
        for(int u:g[v])
            if (u != pv){
                dfs(u, v);
                if (col[v].size() < col[u].size())
                    swap(col[v], col[u]);
                for(int x:col[u])
                    col[v].insert(x);
            }
        ans[v] = col[v].size();
    };
    dfs(0, 0);
    for(int i = 1; i <= n; ++i) cout<<ans[i]<<'\n';
    return 0;
}

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