제출 #972744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972744		Gangsta	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	197 ms	17656 KiB

bridge

#include "bits/stdc++.h"
#define ll long long int
#define pb push_back
#define pii pair<ll,ll>
#define ff first
#define ss second
#define sz size()

const int N = 2e5 + 1;

using namespace std;

ll n, k, x[N], y[N], ans, p[N], q[N], mn = 1e15, cnt, cnt1, sum, sum1;

char s[N], d[N];

vector <pii> v;

multiset <int> l, r;

bool cmp(pii a, pii b) {
	return a.ff + a.ss < b.ff + b.ss;
}

void med(int a){
	if(l.empty()) {
		l.insert(a);
		sum += a;
	}
	else if((int)l.sz <= (int)r.sz){
		auto t = r.begin();
		ll aa = *t;
		if (a > aa) {
			sum += aa;
			l.insert(aa);
			sum1 += a;
			sum1 -= aa;
			r.erase(t);
			r.insert(a);
		}
		else {
			l.insert(a);
			sum += a;
		}
	}
	else{
		auto t = l.end();
		t--;
		ll aa = *t;
		if (a < aa){
			sum -= (ll)aa;
			sum += a;
			sum1 += aa;
			r.insert(aa);
			l.erase(t);
			l.insert(a);
		}
		else{
			r.insert(a);
			sum1 += a;
		}
	}
}

int main() {
//	freopen ("input.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> k >> n;
    for(int i = 1; i <= n; i++){
    	cin >> s[i] >> x[i] >> d[i] >> y[i];
    	if(s[i] != d[i]){
    		ans++;
    		v.pb({x[i],y[i]});
    	}
    	else ans += abs(x[i]-y[i]);
    }
    sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < (int)v.sz; i++){
    	med(v[i].ff);
		med(v[i].ss);
		auto t = l.end();
    	t--;
    	ll med1 = *t;
    	cnt = (int)l.sz;cnt1 = (int)r.sz;
    	p[i] = (cnt * med1 - sum) + (sum1 - cnt1 * med1);
    }
    cnt = sum = cnt1 = sum1 = 0;
    l.clear();r.clear();
    for(int i = (int)v.sz-1; i >= 0; i--){
		med(v[i].ff);
		med(v[i].ss);
		auto t = l.end();
    	t--;
    	ll med1 = *t;
    	cnt = (int)l.sz;cnt1 = (int)r.sz;
    	q[i] = (cnt * med1 - sum) + (sum1 - cnt1 * med1);
    }
    for(int i = 0; i < (int)v.sz; i++){
    	mn = min(mn, p[i] + q[i+1]);
    }
    mn = min(mn,q[0]);
    if(k == 1) mn = q[0];
    cout << mn + ans;
}

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