Submission #978239

#	Time	Username	Problem	Language	Result	Execution time	Memory
978239		nnin	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	464 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 check(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<pii> sweep;
    for(auto [st, en]:cross) {
        sweep.push_back({st, 1});
        sweep.push_back({en, 0});
        sweep.push_back({en+1, -1});
    }
    sort(sweep.begin(), sweep.end());
    int val = 0, mn = 2e9, mx = -1, cur = 0;
    for(int i=0;i<sweep.size();i++) {
        cur += sweep[i].s;
        if(i+1<sweep.size() && sweep[i+1].f==sweep[i].f) continue;
        if(cur>val) {
            val = cur; mn = mx = sweep[i].f;
        } else if(cur==val) {
            mx = sweep[i].f;
        }
    }
    if((mn+mx)%2==0) return check((mn+mx)/2);
    return min(check((mn+mx)/2), check((mn+mx+1)/2));
}

ll two() {
    return one();
}

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(z1==z2) {
            ans += abs(b1-b2);
        } else {
            cross.push_back({min(b1, b2), max(b1, b2)});
        }
    }
    ans += cross.size();
    if(K==1) cout<<ans+one();
    else cout<<ans+two();
}

Compilation message (stderr)

bridge.cpp: In function 'll one()':
bridge.cpp:30: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]
   30 |     for(int i=0;i<sweep.size();i++) {
      |                 ~^~~~~~~~~~~~~
bridge.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if(i+1<sweep.size() && sweep[i+1].f==sweep[i].f) continue;
      |            ~~~^~~~~~~~~~~~~

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