Submission #111186

#	Time	Username	Problem	Language	Result	Execution time	Memory
111186		oToToT	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	310 ms	20440 KiB

bridge

/*
0 0 : 
0 1
1 1
*/
#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;

int k, n;
lld ans;
vector< pair< int, int > > seg;
vector< int > pos;

void init() {
	cin >> k >> n;
	seg.reserve( n );
	for ( int i = 0 ; i < n ; ++ i ) {
		string P; int S;
		string Q; int T;
		cin >> P >> S >> Q >> T;
		ans += ( P == Q ? abs( S - T ) : 1 );
		if ( P != Q ) seg.push_back( minmax( S, T ) );
	}
	pos.reserve( seg.size() << 1 );
	for ( auto [ L, R ] : seg )
		pos.push_back( L ),
		pos.push_back( R );
}

struct Data{
	lld val; int P, Q;
	priority_queue< pair< int, size_t > >
		LPRQ, PLR, LRQ, PLQR, PQLR;
	vector< size_t > LRPQ;
	lld sLRPQ, sLPRQ, sPLR, sLRQ, sPLQR, sPQLR;
	Data() : val( 0 ), sLRPQ( 0 ),
		sLPRQ( 0 ), sPLR( 0 ), 
		sLRQ( 0 ), sPLQR ( 0 ), 
		sPQLR( 0 ) {}
	void calcVal() {
		val = 0;
		val += sPQLR - ( ( lld ) 2 ) * Q * PQLR.size();
		val += sPLQR;
		val += ( ( lld ) 2 ) * Q * LRQ.size() - sLRQ;
		val += sPLR - ( ( lld ) 2 ) * P * PLR.size();
		val += sLPRQ;
		val += ( ( lld ) 2 ) * P * LRPQ.size() - sLRPQ;
	}
	void build() {
		P = pos[ 0 ], Q = pos[ 0 ];
		for ( size_t i = 0 ; i < seg.size() ; ++ i ) {
			PQLR.push( { -seg[ i ].first, i } );
			sPQLR += seg[ i ].first + seg[ i ].second;
		}
		calcVal();
	}
	void adjustPQLR() {
		while ( not PQLR.empty() ) {
			if ( -PQLR.top().first > Q )
				break;
			size_t idx = PQLR.top().second; PQLR.pop();
			sPQLR -= seg[ idx ].first + seg[ idx ].second;
			PLQR.push( { -seg[ idx ].second, idx } );
			sPLQR += seg[ idx ].second - seg[ idx ].first;
		}
	}
	void adjustPLQR() {
		while ( not PLQR.empty() ) {
			if ( -PLQR.top().first > Q )
				break;
			size_t idx = PLQR.top().second; PLQR.pop();
			sPLQR -= seg[ idx ].second - seg[ idx ].first;
			LRQ.push( { - seg[ idx ].first - seg[ idx ].second, idx } );
			sLRQ += seg[ idx ].first + seg[ idx ].second;
		}
	}
	void adjustLRQ() {
		while ( not LRQ.empty() ) {
			if ( -LRQ.top().first > ( P + Q ) )
				break;
			size_t idx = LRQ.top().second; LRQ.pop();
			sLRQ -= seg[ idx ].first + seg[ idx ].second;
			PLR.push( { -seg[ idx ].first, idx } );
			sPLR += seg[ idx ].first + seg[ idx ].second;
		}
	}
	void adjustPLR() {
		while ( not PLR.empty() ) {
			if ( -PLR.top().first > P )
				break;
			size_t idx = PLR.top().second; PLR.pop();
			sPLR -= seg[ idx ].first + seg[ idx ].second;
			LPRQ.push( { -seg[ idx ].second, idx } );
			sLPRQ += seg[ idx ].second - seg[ idx ].first;
		}
	}
	void adjustLPRQ() {
		while ( not LPRQ.empty() ) {
			if ( -LPRQ.top().first > P )
				break;
			size_t idx = LPRQ.top().second; LPRQ.pop();
			sLPRQ -= seg[ idx ].second - seg[ idx ].first;
			LRPQ.push_back( idx );
			sLRPQ += seg[ idx ].first + seg[ idx ].second;
		}
	}
	void addP( int x ) {
		P = x;
		adjustPQLR();
		adjustPLQR();
		adjustLRQ();
		adjustPLR();
		adjustLPRQ();
		calcVal();
	}
	void addQ( int x ) {
		Q = x;
		adjustPQLR();
		adjustPLQR();
		adjustLRQ();
		adjustPLR();
		adjustLPRQ();
		calcVal();
	}
	friend ostream& operator<<( ostream& os, const Data& d ) {
		return os << "P = " << d.P << ", Q = " << d.Q << ", val = " << d.val << ", sLRPQ = " << d.sLRPQ << ", sLPRQ = " << d.sLPRQ << ", sPLR = " << d.sPLR << ", sLRQ = " << d.sLRQ << ", sPLQR = " << d.sPLQR << ", sPQLR = " << d.sPQLR;
	}
} cur, nxt;

function< void() > solve[] = {
	[] () {
		nth_element( pos.begin(), next( pos.begin(), pos.size() >> 1 ), pos.end() );
		for ( int x : pos )
			ans += abs( x - *next( pos.begin(), pos.size() >> 1 ) );
	},
	[] () {
		if ( pos.size() < 2 ) {
			solve[ 0 ]();
			return;
		}
		lld dlt = numeric_limits< lld >::max();
		sort( pos.begin(), pos.end() );
		cur.build();
		nxt.build();
		cur.addQ( pos[ 0 ] );
		nxt.addQ( pos[ 1 ] );
		size_t Q = 0;
		for ( size_t P = 0 ; P < pos.size() ; ++ P ) {
			while ( Q < P ) {
				cur.addQ( pos[ ++ Q ] );
				if ( Q + 1 < pos.size() )
					nxt.addQ( pos[ Q + 1 ] );
			}
			cur.addP( pos[ P ] );
			nxt.addP( pos[ P ] );
			while ( Q + 1 < pos.size() and cur.val >= nxt.val ) {
				cur.addQ( pos[ ++ Q ] );
				if ( Q + 1 < pos.size() )
					nxt.addQ( pos[ Q + 1 ] );
			}
			dlt = min( dlt, cur.val );
			// cout << "cur: " << cur << '\n';
			// cout << "nxt: " << nxt << '\n';
		}
		ans += dlt;
	}
};

int main() {
	ios_base::sync_with_stdio( false );
	cin.tie( nullptr );
	init();
	solve[ k - 1 ]();
	cout << ans << '\n';
	return 0;
}
/*

L R P Q -> R <= P                                        P - L + P - R
L P R Q -> L <= P and P <= R                             R - L
P L R Q -> P <= L and R <= Q and ( L + R ) <= ( P + Q )  L - P + R - P
P L R Q -> P <= L and R <= Q and ( L + R ) >= ( P + Q )  Q - R + Q - L
P L Q R -> L <= Q and Q <= R                             R - L
P Q L R -> Q <= L                                        L - Q + R - Q

( L + R ) <= ( P + Q )

*/

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