Submission #1307698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307698		JuanJL	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	268 ms	27020 KiB

bridge

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define forn(i,a,b) for(int i = a; i< b; i++)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

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

ll k,n;

vector<ll> laderach(vector<pair<ll,ll>> rng){
	
	
		imset<pair<ll,ll>> left;
		imset<pair<ll,ll>> right;
		multiset<ll> vals; vals.insert(-1);
		auto it = vals.begin();
		ll aux = 0;
		vector<ll> ltr(SZ(rng),0);
		vector<ll> rtl(SZ(rng),0);
		ll resaux=0;
		forn(i,0,SZ(rng)){
			left.insert({rng[i].fst,aux}); aux++;
			right.insert({rng[i].snd,aux}); aux++;
			vals.insert(rng[i].fst);
			vals.insert(rng[i].snd);
	
			resaux+=(rng[i].fst-(*it))*2;

			while(true){
			ll cleft=0;
			auto lait = left.lower_bound({*it+1,-1});
			if(lait!=left.end()){
				cleft=SZ(left)-left.order_of_key(*lait);			
			}
	
			ll cright=SZ(right);
			auto rait = right.upper_bound({*it,1000000000000000});
			if(rait!=right.end()){
				cright=right.order_of_key(*rait);
			}
	
			if(cleft>cright){
				ll last=*it; it++;
				ll neww = *it;
				resaux+=(neww-last)*2*cright;
				resaux-=(neww-last)*2*cleft;
			}else{
				break;
			}
			}
	
			ltr[i]=resaux;
			//cout<<resaux<<" "<<i<<'\n';
		}
		if(k==1) return ltr;
	aux = 0;
	forn(i,0,SZ(rng)-1){
					left.erase({rng[i].fst,aux}); aux++;
					right.erase({rng[i].snd,aux}); aux++;
					if(vals.begin()==it) it++;
					vals.erase(vals.begin());
					if(vals.find(rng[i].snd)==it) it++;
					vals.erase(vals.find(rng[i].snd)); 
			
					resaux-=(max((ll)0,(*it)-rng[i].snd))*2;
					//while(true){
					ll cleft=0;
					auto lait = left.lower_bound({*it+1,-1});
					if(lait!=left.end()){
						cleft=SZ(left)-left.order_of_key(*lait);			
					}
			
					ll cright=SZ(right);
					auto rait = right.upper_bound({*it,1000000000000000});
					if(rait!=right.end()){
						cright=right.order_of_key(*rait);
					}
			
					if(cleft>cright){
						ll last=*it; it++;
						ll neww = *it;
						resaux+=(neww-last)*2*cright;
						resaux-=(neww-last)*2*cleft;
					}
			
					rtl[i]=resaux;
					//cout<<resaux<<" "<<i<<'\n';
				}
				rtl[SZ(rng)-1]=0;
		vector<ll> res(SZ(rng));
		forn(i,0,SZ(rng)){
			res[i]=ltr[i]+(SZ(rng)-(i+1)>=0?rtl[SZ(rng)-(i+1)]:0);
		}
		return res;
}

int main(){
	cin>>k>>n;

	vector<pair<ll,ll>> rng;
	ll resbase = 0;
	forn(i,0,n){
		char a,b; 
		ll l; ll r;
		cin>>a>>l>>b>>r;
		if(l>r) swap(l,r);
		if(a!=b){
			rng.pb({l,r});
			resbase++;
		}
		resbase+=r-l;
	}

	sort(ALL(rng));

	vector<ll> resltr = laderach(rng);

	ll mini = 10000000000000000;
	if(k==2) forn(i,0,SZ(rng)) mini=min(mini,resltr[i]);
	else mini=(SZ(rng)>0?resltr[SZ(rng)-1]:0);
	if(SZ(rng)==0) cout<<resbase<<'\n';
	else cout<<mini+resbase<<'\n';
	return 0;
}

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