Submission #1254686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254686		minhpk	Collapse (JOI18_collapse)	C++20	0 / 100	16 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;

struct Interval { int u, v, l, r; };
vector<Interval> intervals;
vector<vector<pii>> pos;
vector<vector<pii>> seg_pref, seg_suf;

struct ST {
    int n;
    vector<int> f, lazy;
    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]) return;
        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 stree;

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];
struct Roll { int y, sy, id, type, w; };
vector<Roll> roll_stack;

int findp(int u) { return par[u]==u ? u : findp(par[u]); }
bool join(int u, int v, int id, int type) {
    int x = findp(u), y = findp(v);
    if (x == y) return false;
    if (sz[x] < sz[y]) swap(x,y);
    roll_stack.push_back({y, sz[y], id, type, (type==1? max(u,v): min(u,v))});
    par[y] = x;
    sz[x] += sz[y];
    return true;
}

void rollback(int id) {
    while (!roll_stack.empty() && roll_stack.back().id == id) {
        auto R = roll_stack.back();
        roll_stack.pop_back();
        int y = R.y, sy = R.sy;
        int type = R.type, w = R.w;
        int x = par[y];
        sz[x] -= sy;
        par[y] = y;
        // undo segment-tree update
        if (type == 1) {
            stree.update(1, 0, a-1, w, a-1, +1);
        } else {
            stree.update(1, 0, a-1, 0, w, +1);
        }
    }
}

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 &e : seg_pref[id]) {
        if (join(e.first, e.second, id, 1)) {
            int wv = max(e.first, e.second);
            stree.update(1, 0, a-1, wv, a-1, -1);
        }
    }
    if (l == r) {
        for (auto &pr : pos[l]) res[pr.second] = stree.get(1,0,a-1,pr.first);
    } else {
        int m=(l+r)>>1;
        dfs_pref(id*2, l, m);
        dfs_pref(id*2+1, m+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 &e : seg_suf[id]) {
        if (join(e.first, e.second, id, 2)) {
            int wv = min(e.first, e.second);
            stree.update(1, 0, a-1, 0, wv, -1);
        }
    }
    if (l == r) {
        for (auto &pr : pos[l]) res[pr.second] += stree.get(1,0,a-1,pr.first);
    } else {
        int m=(l+r)>>1;
        dfs_suf(id*2, l, m);
        dfs_suf(id*2+1, m+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 { intervals.push_back({e.first,e.second,last[e],i-1}); last.erase(e); }
    }
    for (auto &p:last) intervals.push_back({p.first.first,p.first.second,p.second,b-1});
    for (auto &I: intervals) {
        add_interval(seg_pref,1,0,b-1,I.l,I.r,{I.u,I.v});
        add_interval(seg_suf,1,0,b-1,I.l,I.r,{I.u,I.v});
    }
    for (int i=0;i<c;i++) pos[w1[i]].push_back({w[i],i});
    
    stree.init(a);
    for (int x=0;x<a;x++) stree.update(1,0,a-1,x,a-1,1);
    iota(par,par+a,0);
    fill(sz,sz+a,1);
    dfs_pref(1,0,b-1);

    stree.init(a);
    for (int x=0;x<a;x++) stree.update(1,0,a-1,0,x,1);
    iota(par,par+a,0);
    fill(sz,sz+a,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