Submission #1127493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127493		underwaterkillerwhale	Plahte (COCI17_plahte)	C++20	160 / 160	268 ms	45524 KiB

plahte

//#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define REB(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 3e5 + 7;
const int Mod = 1e9 + 7;///lon
const ll INF = 1e18 + 7;
const ll BASE = 137;
const int szBL = 450;

struct Event {
    int typ, X, u, v, id;
};

struct Segment_Tree {
    int m;
    int st[N << 2], lz[N << 2];

    void init (int n) {
        m = n;
        rep (i, 1, n << 2) lz[i] = -1;
    }

    void down (int id) {
        rep (i, id << 1, id << 1 | 1) {
            st[i] = lz[id];
            lz[i] = lz[id];
        }
        lz[id] = -1;
    }

    void update (int id, int l, int r, int u, int v, int pos) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            lz[id] = pos;
            st[id] = pos;
            return;
        }
        int mid = l + r >> 1;
        if (lz[id] != -1) down(id);
        update (id << 1, l, mid, u, v, pos);
        update (id << 1 | 1, mid + 1, r, u, v, pos);
    }

    int get (int id, int l, int r, int pos) {
        if (l > pos || r < pos) return 0;
        if (l == r) return st[id];
        int mid = l + r >> 1;
        if (lz[id] != -1) down(id);
        return max(get(id << 1, l, mid, pos) , get (id << 1 | 1, mid + 1, r, pos));
    }

    void update (int u, int v, int pos) {
        update (1, 1, m, u, v, pos);
    }
    int get (int pos) {
        return get (1, 1, m, pos);
    }
}ST;

int n, m;
vector<Event> evn;

vector<int> ke[N];
int par[N];

int vis[N];
set<int> S[N];

void solution() {
    cin >> n >> m;
    vector<int> vecY;
    rep (i, 1, n) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        evn.pb({0, x, y, v, i});
        evn.pb({2, u, y, v, i});
        vecY.pb(y);
        vecY.pb(v);
    }
    rep (i, 1, m) {
        int x, y, k;
        cin >> x >> y >> k;
        evn.pb({1, x, y, y, k});
        vecY.pb(y);
    }
    int szY = 0;
    sort (ALL(vecY));
    vecY.resize(szY = unique(ALL(vecY)) - vecY.begin());
    iter (&cur, evn) {
        cur.u = lower_bound(ALL(vecY), cur.u) - vecY.begin() + 1;
        cur.v = lower_bound(ALL(vecY), cur.v) - vecY.begin() + 1;
    }
    sort (ALL(evn), [] (Event A, Event B) { return A.X < B.X || (A.X == B.X && A.typ < B.typ); });
    ST.init(szY);
    iter (&cur, evn) {
        int typ = cur.typ, u = cur.u, v = cur.v, id = cur.id;
        if (typ == 0) {
            par[id] = ST.get(u);
            ST.update(u, v , id);
        }
        else if (typ == 2) {
            ST.update(u, v, par[id]);
        }
        else {
            S[ST.get(u)].insert(id);
        }
    }
    rep (i, 1, n) {
        ke[par[i]].pb(i);
    }
    vector<int> Ans(n + 3, 0);
    function<void(int)> dfs = [&] (int u) {
        vis[u] = 1;
        iter (&v, ke[u]) {
            if (!vis[v])
                 dfs(v);
            if (SZ(S[u]) < SZ(S[v])) swap(S[u], S[v]);
            iter (&id, S[v]) S[u].insert(id);
            set<int> ().swap(S[v]);
        }
        Ans[u] = SZ(S[u]);
    };
    rep (i, 1, n) if (!vis[i]) dfs(i);
    rep (i, 1, n) cout << Ans[i] <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +36

*/

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