Submission #982897

#	Time	Username	Problem	Language	Result	Execution time	Memory
982897		tamir1	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	39 ms	5844 KiB

bridge

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
ll ans,n,k,i,j,x,y,l,m,a[200005],z,mn=1e18,a1,a2,m1,m2;
vector<pair<ll,ll>> v;
char s,t;
bool cmp(pair<ll,ll> a,pair<ll,ll> b){
	return a.ff+a.ss<b.ff+b.ss;
}
ordered_set p,q;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> k >> n;
	for(i=1;i<=n;i++){
		cin >> s >> x >> t >> y;
		if(s==t) ans+=abs(x-y);
		else{
			ans++;
			l++;
			a[l]=x;
			l++;
			a[l]=y;
			if(x>y) swap(x,y);
			v.push_back({x,y});
		}
	}
	sort(a+1,a+l+1);
	x=a[(l+1)/2];
	if(k==1){
	for(i=1;i<=l;i++){
		ans+=abs(x-a[i]);
	}
	cout << ans;
	return 0;}
	sort(v.begin(),v.end(),cmp);
	if(v.size()==0){
		cout << ans;
		return 0;
	}
	if(v.size()==1){
		cout << ans+v[0].ss-v[0].ff;
		return 0;
	}
	p.insert(v[0].ff);
	p.insert(v[0].ss);
	for(i=1;i<v.size();i++){
		q.insert(v[i].ff);
		q.insert(v[i].ss);
	}
	m1=*p.find_by_order(p.size()/2);
	m2=*q.find_by_order(q.size()/2);
	for(auto it=p.begin();it!=p.end();it++) a1+=abs(*it-m1);
	for(auto it=q.begin();it!=q.end();it++) a2+=abs(*it-m2);
	mn=min(mn,a1+a2);
	for(i=1;i<v.size()-1;i++){
		ll x=v[i].ff,y=v[i].ss;
		p.insert(x);
		m=*p.find_by_order(p.size()/2);
		a1+=abs(x-m1);
		if(p.size()%2==1) a1-=abs(m1-m);
		m1=m;
		p.insert(y);
		m=*p.find_by_order(p.size()/2);
		a1+=abs(y-m1);
		if(p.size()%2==1) a1-=abs(m1-m);
		m1=m;
		q.erase(q.upper_bound(x));
		m=*q.find_by_order(q.size()/2);
		if(q.size()%2==1) a2+=abs(m2-m);
		a2-=(m2-x);
		m2=m;
		q.erase(q.upper_bound(y));
		m=*q.find_by_order(q.size()/2);
		if(q.size()%2==1) a2+=abs(m2-m);
		a2-=(m2-y);
		m2=m;
		mn=min(mn,a1+a2);
	}
	cout << ans+mn;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:52:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(i=1;i<v.size();i++){
      |          ~^~~~~~~~~
bridge.cpp:61:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(i=1;i<v.size()-1;i++){
      |          ~^~~~~~~~~~~

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