Submission #1254677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254677		minhpk	Collapse (JOI18_collapse)	C++20	0 / 100	17 ms	4484 KiB

collapse

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

static const int MAXN = 100000;
typedef pair<int,int> pii;

int a, b, c;
vector<int> t, z, z1, w, w1;
vector<int> res;
map<pii,int> m;

struct Edge { int x, y, l, r; };
vector<Edge> vec;
vector<vector<pii>> pos;
vector<vector<pii>> seg_pref, seg_suf;

struct ST {
    int n;
    vector<int> f, lazy;
    ST(int _n=0) { init(_n); }
    void init(int _n) {
        n = _n;
        f.assign(4*n+4, 0);
        lazy.assign(4*n+4, 0);
    }
    void apply(int id, int l, int r, int v) {
        f[id] += v;
        lazy[id] += v;
    }
    void push(int id) {
        if (lazy[id]) {
            apply(id*2, 0, 0, lazy[id]);
            apply(id*2+1, 0, 0, lazy[id]);
            lazy[id] = 0;
        }
    }
    void update(int id, int l, int r, int L, int R, int v) {
        if (R < l || r < L) return;
        if (L <= l && r <= R) {
            apply(id, l, r, v);
            return;
        }
        int mid = (l+r)>>1;
        push(id);
        update(id*2, l, mid, L, R, v);
        update(id*2+1, mid+1, r, L, R, v);
        f[id] = f[id*2] + f[id*2+1];
    }
    int get(int id, int l, int r, int p) {
        if (l == r) return f[id];
        int mid = (l+r)>>1;
        push(id);
        return p <= mid ? get(id*2, l, mid, p) : get(id*2+1, mid+1, r, p);
    }
};

ST f1;

void add_interval(vector<vector<pii>>& seg, int id, int l, int r, int L, int R, pii e) {
    if (R < l || r < L) return;
    if (L <= l && r <= R) {
        seg[id].push_back(e);
        return;
    }
    int mid = (l+r)>>1;
    add_interval(seg, id*2,   l, mid, L, R, e);
    add_interval(seg, id*2+1, mid+1, r, L, R, e);
}

int par[MAXN+5], sz[MAXN+5];
stack<pair<pii,int>> st;
int findp(int u) { return par[u]==u ? u : findp(par[u]); }
bool join(int x, int y, int id) {
    x = findp(x); y = findp(y);
    if (x == y) return false;
    if (sz[x] < sz[y]) swap(x,y);
    st.push({{y, sz[y]}, id});
    par[y] = x;
    sz[x] += sz[y];
    return true;
}
void rollback(int id) {
    while (!st.empty() && st.top().second == id) {
        auto pr = st.top().first;
        int y = pr.first, sy = pr.second;
        st.pop();
        int x = par[y];
        sz[x] -= sy;
        par[y] = y;
    }
}

void dfs_pref(int id, int l, int r) {
    sort(seg_pref[id].begin(), seg_pref[id].end(), [](pii a, pii b){ return max(a.first,a.second) < max(b.first,b.second); });
    for (auto &p : seg_pref[id]) {
        int u=p.first, v=p.second;
        int w = max(u,v);
        if (join(u,v,id)) f1.update(1,0,a-1,w,a-1,-1);
    }
    if (l == r) {
        for (auto &pr : pos[l]) {
            int x = pr.first, qi = pr.second;
            res[qi] = f1.get(1,0,a-1,x);
        }
    } else {
        int mid=(l+r)>>1;
        dfs_pref(id*2, l, mid);
        dfs_pref(id*2+1, mid+1, r);
    }
    rollback(id);
}

void dfs_suf(int id, int l, int r) {
    sort(seg_suf[id].begin(), seg_suf[id].end(), [](pii a, pii b){ return min(a.first,a.second) > min(b.first,b.second); });
    for (auto &p : seg_suf[id]) {
        int u=p.first, v=p.second;
        int w = min(u,v);
        if (join(u,v,id)) f1.update(1,0,a-1,0,w,-1);
    }
    if (l == r) {
        for (auto &pr : pos[l]) {
            int x = pr.first, qi = pr.second;
            res[qi] += f1.get(1,0,a-1,x);
        }
    } else {
        int mid=(l+r)>>1;
        dfs_suf(id*2, l, mid);
        dfs_suf(id*2+1, mid+1, r);
    }
    rollback(id);
}

vector<int> simulateCollapse(int N, vector<int> T_, vector<int> X_, vector<int> Y_, vector<int> W_, vector<int> P_) {
    a = N; b = T_.size(); c = W_.size();
    t = T_; z = X_; z1 = Y_; w = W_; w1 = P_;
    res.assign(c,0);
    pos.assign(b, {});
    seg_pref.assign(4*b+4, {});
    seg_suf.assign(4*b+4, {});
    map<pii,int> last;
    for (int i=0;i<b;i++) {
        pii e={z[i], z1[i]};
        if (t[i]==0) last[e]=i;
        else {
            int j = last[e];
            vec.push_back({e.first,e.second,j,i-1});
            last.erase(e);
        }
    }
    for (auto &p:last) {
        vec.push_back({p.first.first,p.first.second,p.second,b-1});
    }
    for (auto &e:vec) {
        add_interval(seg_pref, 1, 0, b-1, e.l, e.r, {e.x,e.y});
        add_interval(seg_suf, 1, 0, b-1, e.l, e.r, {e.x,e.y});
    }
    for (int i=0;i<c;i++) pos[w1[i]].push_back({w[i],i});
    f1.init(a);
    for (int x=0;x<a;x++) f1.update(1,0,a-1,x,a-1,1);
    for (int i=0;i<a;i++){ par[i]=i; sz[i]=1; }
    dfs_pref(1,0,b-1);
    f1.init(a);
    for (int x=0;x<a;x++) f1.update(1,0,a-1,0,x,1);
    for (int i=0;i<a;i++){ par[i]=i; sz[i]=1; }
    dfs_suf(1,0,b-1);
    return res;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35