Submission #1181395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181395		RandomUser	Plahte (COCI17_plahte)	C++20	160 / 160	329 ms	88004 KiB

plahte

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

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 3e5 + 5;

int n;
vector<int> tree[4*maxn];

void add(int u, int tl, int tr, int l, int r, int v) {
    if(tl > r || l > tr) return ;

    if(l <= tl && tr <= r) {
        tree[u].push_back(v);
        return ;
    }

    int tm = (tl + tr) / 2;
    add(2*u, tl, tm, l, r, v);
    add(2*u+1, tm+1, tr, l, r, v);
}

void rem(int u, int tl, int tr, int l, int r) {
    if(tl > r || l > tr) return ;

    if(l <= tl && tr <= r) {
        tree[u].pop_back();
        return ;
    }

    int tm = (tl + tr) / 2;
    rem(2*u, tl, tm, l, r);
    rem(2*u+1, tm+1, tr, l, r);
}

int par = -1;

void get(int u, int tl, int tr, int p) {
    // cout << "! " << tl << " " << tr << " " << p << endl;
    if(!tree[u].empty()) par = tree[u].back();
    if(tl == tr) return ;
    int tm = (tl + tr) / 2;
    if(p <= tm) get(2*u, tl, tm, p);
    else get(2*u+1, tm+1, tr, p);
}

int ans[maxn];
vector<int> G[maxn];
set<int> col[maxn];

void dfs(int u) {
    for(int v : G[u]) {
        dfs(v);
        if(col[u].size() < col[v].size()) swap(col[u], col[v]);
        for(auto x : col[v]) col[u].insert(x);
    }
    ans[u] = col[u].size();
}

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

    int n, q; cin >> n >> q;
    vector<int> a(n+1), b(n+1), c(n+1), d(n+1), x(q+1), y(q+1), k(q+1);
    set<int> st;

    for(int i=1; i<=n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        st.insert(b[i]);
        st.insert(d[i]);
    }

    for(int i=1; i<=q; i++) {
        cin >> x[i] >> y[i] >> k[i];
        st.insert(y[i]);
    }

    vector<ar<int, 3> > E;
    vector<int> cmp(st.begin(), st.end());
    for(int i=1; i<=n; i++) {
        b[i] = lower_bound(cmp.begin(), cmp.end(), b[i]) - cmp.begin();
        d[i] = lower_bound(cmp.begin(), cmp.end(), d[i]) - cmp.begin();
        E.push_back({ a[i], i, 0 });
        E.push_back({ c[i]+1, ~i, 1 });
    }

    for(int i=1; i<=q; i++) {
        y[i] = lower_bound(cmp.begin(), cmp.end(), y[i]) - cmp.begin();
        E.push_back({ x[i], n+i, 2 });
    }

    sort(E.begin(), E.end());

    int m = 2*n + q;
    vector<int> bad(n+1);
    for(auto [p, id, t] : E) {
        if(t == 0) {
            par = -1;
            get(1, 0, m, b[id]);
            if(par != -1) G[par].push_back(id), bad[id] = 1;
            add(1, 0, m, b[id], d[id], id);
        } else if(t == 1) {
            id = ~id;
            rem(1, 0, m, b[id], d[id]);
        } else {
            id -= n;
            par = -1;
            get(1, 0, m, y[id]);
            if(par != -1) col[par].insert(k[id]); 
        }
    }

    for(int i=1; i<=n; i++) if(!bad[i]) dfs(i);
    for(int i=1; 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