Submission #331989

#	Time	Username	Problem	Language	Result	Execution time	Memory
331989		tzxydby	Palembang Bridges (APIO15_bridge)	C++11	63 / 100	2039 ms	21676 KiB

bridge

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
struct fhq
{
	int rt,c,lc[N],rc[N],sz[N],v[N],sum[N],r[N];
	void pushup(int k)
	{
		sz[k]=sz[lc[k]]+sz[rc[k]]+1;
		sum[k]=sum[lc[k]]+sum[rc[k]]+v[k];
	}
	int newnode(int val)
	{
		c++;
		sz[c]=1,v[c]=sum[c]=val;
		r[c]=rand();
		return c;
	}
	int merge(int a,int b)
	{
		if(!a||!b)
			return a^b;
		if(r[a]<r[b])
		{
			rc[a]=merge(rc[a],b);
			pushup(a);
			return a;
		}
		else
		{
			lc[b]=merge(a,lc[b]);
			pushup(b);
			return b;
		}
	}
	void split(int k,int val,int &a,int &b)
	{
		if(!k)
		{
			a=b=0;
			return;
		}
		if(v[k]<=val)
		{
			a=k;
			split(rc[k],val,rc[k],b);
		}
		else
		{
			b=k;
			split(lc[k],val,a,lc[k]);
		}
		pushup(k);
	}
	void Split(int k,int val,int &a,int &b)
	{
		if(!k)
		{
			a=b=0;
			return;
		}
		if(sz[lc[k]]+1<=val)
		{
			a=k;
			Split(rc[k],val-sz[lc[k]]-1,rc[k],b);
		}
		else
		{
			b=k;
			Split(lc[k],val,a,lc[k]);
		}
		pushup(k);
	}
	void add(int val)
	{
		int x,y;
		split(rt,val,x,y);
		rt=merge(merge(x,newnode(val)),y);
	}
	void del(int val)
	{
		int x,y,z;
		split(rt,val-1,x,y);
		split(y,val,y,z);
		y=merge(lc[y],rc[y]);
		rt=merge(x,merge(y,z));
	}
	int sol()
	{
		if(!sz[rt])
			return 0;
		int h=sz[rt]/2,x,y,z;
		Split(rt,h,x,y);
		Split(y,1,y,z);
		int k=v[y],ans=k*sz[x]-sum[x]+sum[z]-k*sz[z];
		rt=merge(x,merge(y,z));
		return ans;
	}
}t1,t2;
int n,k,tot,ans;
struct node
{
	int l,r;
	bool operator<(const node k)const
	{
		return l+r<k.l+k.r;
	}
};
vector<node>a;
signed main()
{
	ios::sync_with_stdio(false);
	cin>>k>>n;
	for(int i=1;i<=n;i++)
	{
		int l,r;
		char p,q;
		cin>>p>>l>>q>>r;
		if(p==q)
			tot+=abs(l-r);
		else
		{
			a.push_back({l,r});
			t2.add(l);
			t2.add(r);
			tot++;
		}
	}
	ans=t1.sol()+t2.sol();
	if(k==1)
	{
		ans+=tot;
		cout<<ans<<endl;
		return 0;
	}
	sort(a.begin(),a.end());
	for(auto i:a)
	{
		int l=i.l,r=i.r;
		t1.add(l);
		t1.add(r);
		t2.del(l);
		t2.del(r);
		ans=min(ans,t1.sol()+t2.sol());
	}
	ans+=tot;
	cout<<ans<<endl;
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 0 / 37