Submission #1190869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190869		boclobanchat	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	111 ms	9032 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=2e5+5;
long long A[MAXN],B[MAXN],val[MAXN],fen[MAXN],ff[MAXN],ct[MAXN];
ii P[MAXN];
int getlog(long long n) { return 63-__builtin_clzll(n); }
bool comp(ii a,ii b) { return a.fi+a.se<b.fi+b.se; }
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
int walk(int n,int val) { int ans=0;for(int i=getlog(n);i+1;i--) if(ans+(1<<i)<=n&&val>fen[ans+(1<<i)]) val-=fen[ans+=(1<<i)];return ans+1; }
void updf(int i,int n,long long val) { for(;i<=n;i+=i&-i) ff[i]+=val; }
long long getf(int i) { long long ans=0;for(;i;i-=i&-i) ans+=ff[i];return ans; }
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int k,n,cnt=0,cc=0;
	cin>>k>>n;
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		char x,y;
		int u,v;
		cin>>x>>u>>y>>v;
		if(u>v) swap(u,v);
		if(x==y) ans+=v-u;
		else ans++,P[++cnt]={u,v},val[++cc]=u,val[++cc]=v;
	}
	sort(val+1,val+cc+1);
	sort(P+1,P+cnt+1,comp);
	if(k==1)
	{
		for(int i=1;i<=cc;i++) ans+=abs(val[cc/2]-val[i]);
		cout<<ans;
	}
	else
	{
		long long aa=1e18;
		for(int i=1;i<=cnt;i++)
		{
			int x=lower_bound(val+1,val+cc+1,P[i].fi)-val;
			int y=lower_bound(val+1,val+cc+1,P[i].se)-val;
			x+=ct[x]++,y+=ct[y]++;
			update(x,cc,1),updf(x,cc,P[i].fi);
			update(y,cc,1),updf(y,cc,P[i].se);
			int med=walk(cc,i);
			A[i]=getf(cc)-getf(med)*2;
		}
		for(int i=1;i<=cc;i++) fen[i]=ff[i]=ct[i]=0;
		for(int i=cnt;i;i--)
		{
			int x=lower_bound(val+1,val+cc+1,P[i].fi)-val;
			int y=lower_bound(val+1,val+cc+1,P[i].se)-val;
			x+=ct[x]++,y+=ct[y]++;
			update(x,cc,1),updf(x,cc,val[x]);
			update(y,cc,1),updf(y,cc,val[y]);
			int med=walk(cc,cnt-i+1);
			B[i]=getf(cc)-getf(med)*2;
		}
		for(int i=0;i<=cnt;i++) aa=min(aa,A[i]+B[i+1]);
		cout<<ans+aa;
	}
}

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