Submission #720276

#	Time	Username	Problem	Language	Result	Execution time	Memory
720276		Boomyday	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	107 ms	2584 KiB

bridge

//
// Created by adavy on 2/12/2023.
//
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

using ost = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>;


// pairs
#define mp make_pair
#define f first
#define s second

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define trav(a,x) for (auto& a: x)


#define all(x) begin(x), end(x)
#define pb push_back


const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);

// TOP > BOTTOM
multiset<ll, greater<ll>> top1, top2;
multiset<ll> bottom1, bottom2;

ll ts1, bs1, ts2, bs2;


void chk(multiset<ll, greater<ll>> top, multiset<ll> bottom, ll ts, ll bs){

    if ((int)top.size()-1 > (int)bottom.size()) {
        ll temp = *top.begin(); top.erase(top.find(temp)); bottom.insert(temp);
        ts-=temp; bs+=temp;
    }
    if ((int)bottom.size() > (int)top.size()) {
        ll temp = *bottom.begin(); bottom.erase(bottom.find(temp)); top.insert(temp);
        bs-=temp; ts+=temp;
    }
}

void ins(ll x, multiset<ll, greater<ll>> top, multiset<ll> bottom, ll ts, ll bs){
    if (top.size()==0) {top.insert(x); ts+=x;}
    else if (x>*top.begin()) {bottom.insert(x); bs+=x;}
    else {top.insert(x); ts+=x;};

    chk(top, bottom, ts, bs);


}

void re(ll x, multiset<ll, greater<ll>> top, multiset<ll> bottom, ll ts, ll bs){
    if (top.find(x) != top.end()) {top.erase(top.find(x)); ts-=x;}
    else {bottom.erase(bottom.find(x)); bs-=x;}
    chk(top, bottom, ts, bs);
}

ll calc(multiset<ll, greater<ll>> top, multiset<ll> bottom, ll ts, ll bs){
    ll m = *top.begin();
    return m*(top.size()) - ts - m*(bottom.size()) + bs;
}

int main(){
    int n, k;
    cin >> k >> n;
    ll leftover = 0;
    vl nums;
    F0R(_, n){
        char l1, l2;
        ll n1, n2;
        cin >> l1 >> n1 >> l2 >> n2;
        if(l1==l2) leftover += abs(n2-n1);
        else {
            nums.pb(n1); nums.pb(n2);
        }

    }
    leftover += nums.size()/2;
    sort(all(nums));
    if(k==1){
        ll md = nums[nums.size()/2];
        //cout << md << endl;
        ll ans = 0;
        trav(i, nums){
            ans += abs(md-i);
        }
        //cout << leftover<< endl;
        cout << ans+leftover<< endl;
    }



}

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