Submission #361435

#	Time	Username	Problem	Language	Result	Execution time	Memory
361435		alireza_kaviani	Palembang Bridges (APIO15_bridge)	C++11	100 / 100	96 ms	9200 KiB

bridge

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll k , n , ans , pref[MAXN] , suff[MAXN] , ps[MAXN] , sum;
priority_queue<ll> pq;
priority_queue<ll , vector<ll> , greater<ll>> pq2;
vector<pll> vec;

void insert(ll x){
	if(SZ(pq) && x < pq.top()) pq.push(x) , sum -= x;
	else	pq2.push(x) , sum += x;
	while(SZ(pq) > SZ(pq2)){
		x = pq.top(); pq.pop(); pq2.push(x);
		sum += 2 * x;
	}
	while(SZ(pq2) > SZ(pq) + 1){
		x = pq2.top(); pq2.pop(); pq.push(x);
		sum -= 2 * x;
	}
	assert(SZ(pq2) >= SZ(pq));
	assert(SZ(pq) == 0 || pq2.top() >= pq.top());
//	exit(0);
}

ll solve(){
	ll x = pq2.top();
	return sum + x * (SZ(pq) - SZ(pq2));
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> k >> n;
	for(int i = 0 ; i < n ; i++){
		string A , B;
		int x , y;
		cin >> A >> x >> B >> y;
		if(A == B){
			ans += abs(x - y);
			continue;
		}
		ans++;
		vec.push_back({x + y , y});
	}
	if(SZ(vec) == 0)	return cout << ans << endl , 0;
	sort(all(vec));
	n = SZ(vec);
//	pq.push(1)a; pq.push(1);
//	cout << SZ(pq) << endl;
	for(int i = 0 ; i < n ; i++){
		insert(vec[i].X - vec[i].Y);
		insert(vec[i].Y);
		pref[i] = solve();
	}
	pq = {};  pq2 = {}; sum = 0;
	for(int i = n - 1 ; i >= 0 ; i--){
		insert(vec[i].X - vec[i].Y);
		insert(vec[i].Y);
		suff[i] = solve();
	}
	ll res = pref[n - 1] + ans;
	for(int i = 0 ; i + 1 < n && k == 2 ; i++){
		res = min(res , pref[i] + suff[i + 1] + ans);
	}
	cout << res << endl;

    return 0;
}
/*

*/

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