Submission #1308321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308321		JuanJL	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	321 ms	23904 KiB

bridge

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

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i< b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;

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

vector<pair<ll,ll>> rng;
set<ll> vals;

ll pA = -1;
ll resauxA = 0;
iset<pair<ll,ll>> leftA;
iset<pair<ll,ll>> rightA;

//acomodar A 
// a partir de la posicion del puente lo acomoda segun sea necesario (izq o der)

void acomodarA(){
	while(true){
		ll cleft=0;
		auto lait = leftA.lower_bound({pA+1,-1});
		if(lait!=leftA.end()){
			cleft=SZ(leftA)-leftA.order_of_key(*lait);			
		}

		ll cright=SZ(rightA);
		auto rait = rightA.upper_bound({pA,1000000000000000});
		if(rait!=rightA.end()){
			cright=rightA.order_of_key(*rait);
		}
		
		if(cleft>cright){
			ll last=pA;
			auto it = vals.lower_bound(pA); it++;
			ll neww = *it;
			resauxA+=(neww-last)*2*cright;
			resauxA-=(neww-last)*2*cleft;
			pA=neww;
		}else{
			break;
		}
	}
}

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

	ll resbase = 0;
	forn(i,0,n){
		char a,b; 
		ll l,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)); vals.insert(-1);
	forn(i,0,SZ(rng)) vals.insert(rng[i].fst),vals.insert(rng[i].snd);
	ll aux = 0;
	forn(i,0,SZ(rng)) leftA.insert({rng[i].fst,aux}), aux++;
	forn(i,0,SZ(rng)) rightA.insert({rng[i].snd,aux}), aux++;

	forn(i,0,SZ(rng)){
		resauxA+=(rng[i].fst+1)*2;
	}
	
	acomodarA();

	cout<<resbase+resauxA<<'\n';
	return 0;
}

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