Submission #1150615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150615		brover29	Collapse (JOI18_collapse)	C++20	0 / 100	17 ms	3400 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=1e5+29;
ll n,pr[N],sz[N],mx[N],mn[N],cnt,st[4*N],z[4*N];
vector<int>w;
bool cmp(ll a,ll b){
	return w[a]<w[b];
}ll get(ll x){
	return (pr[x]==x ? x : pr[x]=get(pr[x]));
}void push(ll v,ll l,ll r){
	ll mid=(r+l)>>1;
	st[v*2]+=(mid-l+1)*z[v];
	st[v*2+1]+=(r-mid)*z[v];
	z[v*2]+=z[v];
	z[v*2+1]+=z[v];
	z[v]=0;
}void upd(ll v,ll l,ll r,ll x,ll y,ll value){
    if(l>y||x>r)return;
    if(x<=l&&r<=y){
        st[v]+=value*(r-l+1);
        z[v]+=value;
        return;
    }
    push(v,l,r);
    ll mid=(r+l)/2;
    upd(v*2,l,mid,x,y,value);
    upd(v*2+1,mid+1,r,x,y,value);
    st[v]=st[v*2]+st[v*2+1];
    return;
}
ll get(ll v,ll l,ll r,ll x,ll y){
    if(l>y||x>r)  {
        return 0;
    }
    if(x<=l&&r<=y){
        return st[v];
    }
    push(v,l,r);
    ll mid=(r+l)/2;
    return get(v*2,l,mid,x,y)+get(v*2+1,mid+1,r,x,y);
}

void upd(ll i,ll x){
	ll l=mn[i];
	ll r=mx[i]-1;
	if(l>r)return;
	upd(1,1,n,l,r,x);
}
void uni(ll v,ll u){
	u=get(u);
	v=get(v);
	if(u==v)return;
	if(sz[v]<sz[u])swap(v,u);
	upd(v,-1);
	upd(u,-1);
	pr[u]=v;
	mx[v]=max(mx[v],mx[u]);
	mn[v]=min(mn[v],mn[u]);
	upd(v,1);
	cnt--;
	sz[v]+=sz[u];
}
vector<int> simulateCollapse(int N,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P) {
	vector<int>ans(W.size());
	n=N;
	w=W;
	vector<ll>A(W.size());
	iota(A.begin(),A.end(),0);
	sort(A.begin(),A.end(),&cmp);
	ll j=-1;
	for(ll i=0;i<n;i++){
		pr[i]=i;
		sz[i]=1;
		mx[i]=mn[i]=i;
	}cnt=n;
	for(ll i:A){
		while(j<W[i]){
			j++;
			uni(X[j],Y[j]);
		}
		ans[i]=get(1,1,n,P[i],P[i])+cnt;
	}
	
	return ans;
}

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