Submission #1054427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054427		idas	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	61 ms	6632 KiB

bridge

#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int N=1e5+10;
int k, n;
ll ans, suff[N];
vector<int> a;
vector<pii> inf;

bool cmp(pii a, pii b) {
    return (a.f+a.s)<(b.f+b.s);
}

ll s[4];
void fix(priority_queue<int> &l, priority_queue<int, vector<int>, greater<int>> &r) {
    while(l.size()>r.size()) {
        int val=l.top(); l.pop();
        r.push(val);
        s[0]-=val; s[1]+=val;
    }
    while(r.size()>l.size()) {
        int val=r.top(); r.pop();
        l.push(val);
        s[0]+=val; s[1]-=val;
    }
}

ll calc() {
    return s[1]-s[0];
}

int main() {
    FAST_IO;
    cin >> k >> n;
    FOR(i, 0, n) {
        char c1, c2; int x1, x2;
        cin >> c1 >> x1 >> c2 >> x2;
        if(c1==c2) {
            ans+=abs(x1-x2);
        }
        else {
            inf.pb({x1,x2});
            a.pb(x1);
            a.pb(x2);
        }
    }
    sort(a.begin(), a.end());
    n=a.size();
    ans+=n/2;
    if(n==0) {
        cout << ans;
        return 0;
    }

    sort(inf.begin(), inf.end(), cmp);

    priority_queue<int> l;
    priority_queue<int, vector<int>, greater<int>> r;
    for(int i=(int)inf.size()-1; i>=0; i--) {
        int val=inf[i].f;
        if(l.empty()) l.push(val), s[0]+=val;
        else {
            int md=l.top();
            if(val>=md) r.push(val), s[1]+=val;
            else l.push(val), s[0]+=val;
        }

        val=inf[i].s;
        int md=l.top();
        if(val>=md) r.push(val), s[1]+=val;
        else l.push(val), s[0]+=val;

        fix(l, r);

        suff[i]=calc();
    }

    if(k==1) {
        cout << suff[0]+ans;
        return 0;
    }

    while(!l.empty()) l.pop();
    while(!r.empty()) r.pop();

    s[0]=s[1]=0;
    ll ret=suff[0]+ans;
    FOR(i, 0, inf.size()) {
        int val=inf[i].f;
        if(l.empty()) l.push(val), s[0]+=val;
        else {
            int md=l.top();
            if(val>=md) r.push(val), s[1]+=val;
            else l.push(val), s[0]+=val;
        }

        val=inf[i].s;
        int md=l.top();
        if(val>=md) r.push(val), s[1]+=val;
        else l.push(val), s[0]+=val;
        fix(l, r);

        // cout << i << ": " << calc() << " " << suff[i+1] << endl;

        ret=min(ret, calc()+ans+suff[i+1]);
    }

    cout << ret;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:3:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
      |                                                ^
bridge.cpp:97:5: note: in expansion of macro 'FOR'
   97 |     FOR(i, 0, inf.size()) {
      |     ^~~

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