Submission #764200

#	Time	Username	Problem	Language	Result	Execution time	Memory
764200		qwerasdfzxcl	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	50 ms	4232 KiB

bridge

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
using namespace std;

typedef long long ll;
const int mx = 100005;

int k, n, m;
ll D[mx], E[mx];

struct People{
    int a, b;
    bool operator < (People z){
        return a + b < z.a + z.b;
    }
} P[mx];

void subpr(ll *V){
    if(!n) return;
    ll dval = abs(P[0].a - P[0].b);
    priority_queue<int> lft;
    priority_queue<int,vector<int>,greater<int>> rgt;

    int brp = P[0].a;
    (P[0].b < brp ? lft.push(P[0].b) : rgt.push(P[0].b));
    V[0] = dval;
    for(int i = 1; i < n; i++){
        dval += abs(brp - P[i].a) + abs(brp - P[i].b);
        P[i].a < brp ? lft.push(P[i].a) : rgt.push(P[i].a);
        P[i].b < brp ? lft.push(P[i].b) : rgt.push(P[i].b);
        while(sz(lft) < sz(rgt)){
            int nbr = rgt.top(); rgt.pop();
            lft.push(brp);
            dval += (ll)(nbr - brp) * (sz(lft) - sz(rgt) - 1);
            brp = nbr;
        }
        while(sz(lft) > sz(rgt) + 1){
            int nbr = lft.top(); lft.pop();
            rgt.push(brp);
            dval += (ll)(brp - nbr) * (sz(rgt) - sz(lft) - 1);
            brp = nbr;
        }
        V[i] = dval;
    }
}

ll off;
void input(){
    scanf("%d %d",&k,&m);
    while(m--){
        char p,q;
        int a,b;
        scanf("%*c%c %d %c %d",&p,&a,&q,&b);
        if(p == q) off += abs(a - b);
        else P[n++] = {a, b};
    }
}

int main(){
    input();
    sort(P,P+n);
    subpr(D);
    if(k == 1) return !printf("%lld\n",D[n-1] + off + n);
    reverse(P,P+n);
    subpr(E);
    ll ans = min(D[n-1], E[n-1]);
    for(int i = 0; i < n - 1; i++){
        ans = min(ans, D[i] + E[n - 2 - i]);
    }
    printf("%lld\n",ans + off + n);
}

Compilation message (stderr)

bridge.cpp: In function 'void input()':
bridge.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d %d",&k,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
bridge.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%*c%c %d %c %d",&p,&a,&q,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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