Submission #978670

#	Time	Username	Problem	Language	Result	Execution time	Memory
978670		nnin	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	34 ms	4816 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
using ll = long long;
#define f first
#define s second
 
vector<pii> cross;
int N, K;
 
ll check1(int bridge) {
    ll ret = 0;
    for(auto [st, en]:cross) {
        if(bridge<st) ret += (ll)st-bridge+en-bridge;
        else if(bridge>en) ret += (ll)bridge-st+bridge-en;
        else ret += (ll)en-st;
    }
    return ret;
}
 
ll one() {
    vector<int> v;
    for(auto [st, en]:cross) {
        v.push_back(st);
        v.push_back(en);
    }
    sort(v.begin(), v.end());
    return min(check1(v[((int)v.size()-1)/2]), check1(v[(int)v.size()/2]));
}

ll val1[100005], val2[100005], suml, sumr;
priority_queue<int> l;
priority_queue<int, vector<int>, greater<int>> r;

void insert(int x) {
    if(l.empty() || x<=l.top()) l.push(x), suml += x;
    else r.push(x), sumr += x;
    if(l.size()>r.size()+1) {
        sumr += l.top();
        suml -= l.top();
        r.push(l.top());
        l.pop();
    }
    if(r.size()>l.size()) {
        suml += r.top();
        sumr -= r.top();
        l.push(r.top());
        r.pop();
    }
}
 
ll two() {
    sort(cross.begin(), cross.end());
    for(int i=0;i<cross.size()-1;i++) {
        insert(cross[i].f); insert(cross[i].s);
        val1[i] = sumr-suml;
    }
    while(!l.empty()) l.pop();
    while(!r.empty()) r.pop();
    suml = sumr = 0;
    for(int i=cross.size()-2;i>=0;i--) {
        insert(cross[i+1].f); insert(cross[i+1].s);
        val2[i] = sumr-suml;
    }
    ll ret = one();
    for(int i=0;i<cross.size()-1;i++) {
        ret = min(ret, val1[i]+val2[i]);
    }
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>K>>N;
    ll ans = 0;
    for(int i=0;i<N;i++) {
        char z1, z2;
        int b1, b2;
        cin>>z1>>b1>>z2>>b2;
        if(b1>b2) swap(b1, b2);
        if(z1==z2) {
            ans += b2-b1;
        } else {
            cross.push_back({b1, b2});
        }
    }
    if(cross.empty()) {
        cout<<ans;
        return 0;
    }
    ans += cross.size();
    if(K==1) cout<<ans+one();
    else cout<<ans+two();
}

Compilation message (stderr)

bridge.cpp: In function 'll two()':
bridge.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<cross.size()-1;i++) {
      |                 ~^~~~~~~~~~~~~~~
bridge.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i=0;i<cross.size()-1;i++) {
      |                 ~^~~~~~~~~~~~~~~

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