Submission #1054342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054342		idas	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2094 ms	11428 KiB

bridge

#pragma GCC optimize("O3")

#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;
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(int in, multiset<int> &a, multiset<int> &b) {
    int tot=a.size()+b.size();
    while(a.size()>(tot+1)/2) {
        int val=*a.rbegin();
        a.erase(a.find(val));
        s[in]-=val;
        b.insert(val);
        s[in+1]+=val;
    }
    while(b.size()>tot/2) {
        int val=*b.begin();
        b.erase(b.find(val));
        s[in+1]-=val;
        a.insert(val);
        s[in]+=val;
    }
}

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

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;
    }
    multiset<int> l, r, le, ri;
    sort(inf.begin(), inf.end(), cmp);
    FOR(i, 0, inf.size()) {
        le.insert(inf[i].f);
        le.insert(inf[i].s);
        s[2]+=inf[i].f+inf[i].s;
    }
    while(le.size()>(le.size()+ri.size()+1)/2) {
        int val=*le.rbegin();
        le.erase(le.find(val));
        ri.insert(val);
        s[2]-=val; s[3]+=val;
    }

    ll ret=calc()+ans;

    if(k==1) {
        cout << ret;
        return 0;
    }

    FOR(i, 0, inf.size()) {
        int val=inf[i].f;
        if(l.empty()) l.insert(val), s[0]+=val;
        else {
            int md=*l.rbegin();
            if(val>=md) r.insert(val), s[1]+=val;
            else l.insert(val), s[0]+=val;
        }

        if(le.count(val)) le.erase(le.find(val)), s[2]-=val;
        else ri.erase(ri.find(val)), s[3]-=val;

        val=inf[i].s;
        if(l.empty()) l.insert(val), s[0]+=val;
        else {
            int md=*l.rbegin();
            if(val>=md) r.insert(val), s[1]+=val;
            else l.insert(val), s[0]+=val;
        }

        if(le.count(val)) le.erase(le.find(val)), s[2]-=val;
        else ri.erase(ri.find(val)), s[3]-=val;

        fix(0, l, r);
        fix(2, le, ri);

        ret=min(ret, ans+calc());
    }
    cout << ret;
}

Compilation message (stderr)

bridge.cpp: In function 'void fix(int, std::multiset<int>&, std::multiset<int>&)':
bridge.cpp:28:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |     while(a.size()>(tot+1)/2) {
      |           ~~~~~~~~^~~~~~~~~~
bridge.cpp:35:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |     while(b.size()>tot/2) {
      |           ~~~~~~~~^~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:5: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]
    5 | #define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
      |                                                ^
bridge.cpp:72:5: note: in expansion of macro 'FOR'
   72 |     FOR(i, 0, inf.size()) {
      |     ^~~
bridge.cpp:5: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]
    5 | #define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
      |                                                ^
bridge.cpp:91:5: note: in expansion of macro 'FOR'
   91 |     FOR(i, 0, inf.size()) {
      |     ^~~

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