Submission #972148

#	Time	Username	Problem	Language	Result	Execution time	Memory
972148		Halym2007	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	16 ms	13404 KiB

bridge

#include "bits/stdc++.h"
#define ll long long int
#define pb push_back
#define pii pair<int,int>
#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;
vector <int> v1;

multiset <int> l, r;

bool cmp(pii a, pii b){
	if(a.ff + a.ss <= b.ff + b.ss) return 1;
	else return 0;
}

int med(int a, int b){
	cnt++;cnt1++;
	if(l.empty()){
		sum += a, sum1 += b;
		l.insert(a);
		r.insert(b);
		return a;
	}
	auto t = r.begin();
	if(a > *t){
		l.insert(*t);
		sum += *t;
		sum1 -= *r.begin();
		sum1 += a;
		r.erase(r.begin());
		r.insert(a);
	}
	else{
		l.insert(a);
		sum += a;
	}

	t = l.end();
	t--;
	if(b < *t){
		r.insert(*t);
		sum1 += *t;
		sum -= *t;
		sum += b;
		l.erase(*t);
		l.insert(b);
	}
	else{
		r.insert(b);
		sum1 += b;
	}

	t = l.end();
	t--;
	int san = *t;
	return san;
}

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++){
    	int med1 = med(v[i].ff,v[i].ss);
    	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--){
    	int med1 = med(v[i].ff,v[i].ss);
    	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];
    assert (q[0] == p[(int)v.sz - 1]);
    cout << mn + ans;
}

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