Submission #162701

#	Time	Username	Problem	Language	Result	Execution time	Memory
162701		HungAnhGoldIBO2020	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	174 ms	15864 KiB

bridge

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+2;
const int inf=1e18+2;
multiset<pair<int,int> > lis;
pair<int,int> seg[N];
long long val_pre[N],ans=0,val_suf[N],sum,sum1,val;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int num,i,j,k,l,n,m=0,cnt=0,min1=inf;
	cin>>num>>n;
	char x,y;
	for(i=1;i<=n;i++){
		cin>>x>>j>>y>>k;
		if(j>k){
			swap(j,k);
		}
		if(x!=y){
			ans++;
			m++;
			seg[m].first=j;
			seg[m].second=k;
		}
		else{
			ans+=k-j;
		}
	}
	sort(seg+1,seg+1+m,[&](pair<int,int> x,pair<int,int> y){
		return x.first+x.second<y.first+y.second;
	});
	lis.insert({-inf,0});
	multiset<pair<int,int> >::iterator ite=lis.begin();
	sum=0;
	sum1=0;
	cnt=0;
	val=-inf;
	for(i=m;i>0;i--){
		sum+=seg[i].first;
		sum+=seg[i].second;
		//cout<<seg[i].first<<' '<<seg[i].second<<endl;
		if(seg[i].first<val){
			cnt++;
			sum1+=seg[i].first;
		}
		if(seg[i].second<val){
			cnt++;
			sum1+=seg[i].second;
		}
		lis.insert({seg[i].first,m-i+1});
		lis.insert({seg[i].second,m-i+1});
		while(cnt<m-i+1){
			ite++;
			cnt++;
			sum1+=ite->first;
		}
		while(cnt>m-i+1){
			sum1-=ite->first;
			ite--;
			cnt--;
		}
		val_suf[i]=sum-2*sum1;
		val=ite->first;
		//cout<<sum<<' '<<sum1<<' '<<val<<endl;
	}
	if(num==1){
//		cout<<val_suf[1]<<endl;
		cout<<val_suf[1]+ans;
		return 0;
	}
	lis.clear();
	sum=0;
	sum1=0;
	cnt=0;
	val=-inf;
	lis.insert({-inf,0});
	ite=lis.begin();
	for(i=1;i<=m;i++){
		sum+=seg[i].first;
		sum+=seg[i].second;
		if(seg[i].first<val){
			cnt++;
			sum1+=seg[i].first;
		}
		if(seg[i].second<val){
			cnt++;
			sum1+=seg[i].second;
		}
		lis.insert({seg[i].first,i});
		lis.insert({seg[i].second,i});
		while(cnt<i){
			ite++;
			cnt++;
			sum1+=ite->first;
		}
		while(cnt>i){
			sum1-=ite->first;
			ite--;
			cnt--;
		}
		val_pre[i]=sum-2*sum1;
		val=ite->first;
		//cout<<sum<<' '<<sum1<<' '<<val<<endl;
	}
	for(i=1;i<=m;i++){
		min1=min(min1,val_pre[i]+val_suf[i+1]);
	}
	cout<<ans+min1;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
2 5
B 0 A 4 
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:12:16: warning: unused variable 'l' [-Wunused-variable]
  int num,i,j,k,l,n,m=0,cnt=0,min1=inf;
                ^

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