Submission #969752

#	Time	Username	Problem	Language	Result	Execution time	Memory
969752		pcc	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	553 ms	24688 KiB

bridge

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define int ll

template<typename T> 
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int mxn = 2e5+10;
int N,K;

struct BIT{
	ll bit[mxn];
	BIT(){}
	void modify(int p,int v){
		for(;p<mxn;p+=p&-p)bit[p] += v;
		return;
	}
	ll getval(int s,int e){
		ll re = 0;
		for(;e>0;e-= e&-e)re += bit[e];
		s--;
		for(;s>0;s-= s&-s)re -= bit[s];
		return re;
	}
};

namespace S1{
	vector<ll> v;
	void GO(){
		ll ans = 0;
		for(int i = 0;i<N;i++){
			char s1,s2;
			int p1,p2;
			cin>>s1>>p1>>s2>>p2;
			if(s1 == s2)ans += abs(p2-p1);
			else{
				v.push_back(p1);
				v.push_back(p2);
			}
		}
		sort(v.begin(),v.end());
		ll cen = 0;
		if(!v.empty())cen = v[v.size()/2];
		for(auto &i:v)ans += abs(cen-i);
		ans += v.size()>>1;
		cout<<ans<<'\n';
		return;
	}
}

namespace S2{
	vector<int> all;
	struct DS{
		DS(){}
		BIT cnt,sum;
		ordered_set<pii> st;
		int ptr = 0;
		void add(int k){
			st.insert(pii(k,ptr++));
			cnt.modify(k,1);
			sum.modify(k,all[k]);
		}
		void del(int k){
			auto it = st.lower_bound(pii(k,-1));
			st.erase(st.find(*it));
			cnt.modify(k,-1);
			sum.modify(k,-all[k]);
		}
		ll getval(){
			if(st.empty())return 0;
			ll cen = st.find_by_order(st.size()/2)->fs;
			ll lsum = all[cen]*cnt.getval(0,cen)-sum.getval(0,cen);
			ll rsum = sum.getval(cen+1,mxn-1)-all[cen]*cnt.getval(cen+1,mxn-1);
			return lsum+rsum;
		}
	};
	DS dl,dr;
	vector<pll> v;
	void GO(){
		all.push_back(-1);
		ll ans = 0;
		for(int i = 0;i<N;i++){
			char s1,s2;
			int p1,p2;
			cin>>s1>>p1>>s2>>p2;
			if(s1 == s2){
				ans += abs(p1-p2);
			}
			else{
				if(p1>p2)swap(p1,p2);
				all.push_back(p1);
				all.push_back(p2);
				v.push_back(pll(p1,p2));
			}
		}
		sort(all.begin(),all.end());
		all.erase(unique(all.begin(),all.end()),all.end());
		sort(v.begin(),v.end(),[](pll a,pll b){return a.fs+a.sc<b.fs+b.sc;});
		ans += v.size();
		for(auto &i:v){
			i.fs = lower_bound(all.begin(),all.end(),i.fs)-all.begin();
			i.sc = lower_bound(all.begin(),all.end(),i.sc)-all.begin();
			dr.add(i.fs);
			dr.add(i.sc);
		}
		ll tans = 1e18;
		tans = dl.getval()+dr.getval();
		for(auto &i:v){
			dr.del(i.fs);
			dr.del(i.sc);
			dl.add(i.fs);
			dl.add(i.sc);
			tans = min(tans,dl.getval()+dr.getval());
		}
		cout<<ans+tans<<'\n';
		return;
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>K>>N;
	if(K == 1)S1::GO();
	else S2::GO();
}

Compilation message (stderr)

bridge.cpp:129:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  129 | main(){
      | ^~~~

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