Submission #500304

#	Time	Username	Problem	Language	Result	Execution time	Memory
500304		beaconmc	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	442 ms	21412 KiB

bridge

#include <bits/stdc++.h>

typedef long long ll;
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>

ll addlater;
vector<vector<ll> > tings;
ordered_set sustree;
ll rsum, lsum;
ll median, nextmed;
bool cmp(vector<ll> a, vector<ll> b) { return a[0] + a[1] < b[0] + b[1]; };

void insert(ll a, ll b){
    if (a>b) swap(a,b);
    if (sustree.size() !=0) median = *sustree.find_by_order(sustree.size()/2 - 1), nextmed = *sustree.find_by_order(sustree.size()/2);
    else median = a, nextmed = b; 
    

    if (a<=median && b>median) lsum += a, rsum += b;

    else if (a<=median && b<=median) lsum += a+b-median, rsum += median;

    else {
        sustree.insert(a); sustree.insert(b);
        median = *sustree.find_by_order(sustree.size()/2 - 1);
        lsum += median, rsum += a+b-median;
        goto skip;
    }

    sustree.insert(a); sustree.insert(b);
    skip:;
}

int main(){
    ll k, n;
    cin.tie(0)->sync_with_stdio(0);
    cin >> k >> n;
    FOR(i,0,n){
        char a,b;
        ll x,y;
        cin >> a >> x >> b >> y;

        if (a==b) addlater += abs(x-y);
        else tings.push_back({x,y});
    }
    n = tings.size();

    addlater += n;

    ll prefs[100001];

    sort(tings.begin(), tings.end(), cmp);
    rsum = 0; lsum = 0;

    FOR(i,0,n){
        insert(tings[i][0], tings[i][1]);
        prefs[i] = rsum - lsum;
    }
    ll ans = prefs[n-1];

    if (k==2){
        sustree.clear();
        rsum = 0; lsum = 0;
        FORNEG(i, n-1, 0){
            insert(tings[i][0], tings[i][1]);
            ans = min(ans, rsum - lsum + prefs[i-1]);
        }
    }
    cout << ans + addlater;
}

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