Submission #759252

#	Time	Username	Problem	Language	Result	Execution time	Memory
759252		Username4132	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	46 ms	4956 KiB

bridge

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define F first
#define S second

const int INF=1000000010, MAXN=100010;
int k, n, cnt;
ll ans, res[2][MAXN], base[2*MAXN];
pii arr[MAXN];

struct med{
    set<pii> st;
    set<pii>::iterator itr;
    int pos=0;
    ll prSum=0, sum=0;
    med(){
        st.insert({INF, -1}), st.insert({-INF, -2});
        itr=st.begin();
    }
    void stabilize(){
        int target = (st.size() - 1)/2;
        while(pos > target){
            prSum-=itr->F, --pos, --itr;
        }
        while(pos < target){
            ++pos, ++itr, prSum+=itr->F;
        }
    }

    void insert(pii x){
        st.insert(x);
        if(x < *itr) ++pos, prSum+=x.F;
        sum+=x.F;
        stabilize();
    }


    pii debug(){
        return *itr;
    }

    ll calc(){
        ll off = (st.size()&1)? itr->F : 0;
        return sum - 2*prSum + off;
    }
};

int main(){
    scanf("%d %d", &k, &n);
    forn(i, n){
        char c1, c2;
        int p1, p2;
        scanf(" %c %d %c %d", &c1, &p1, &c2, &p2);
        if(c1==c2) ans+=abs(p1-p2);
        else{
            base[2*cnt]=p1;
            base[2*cnt+1]=p2;
            arr[cnt++]={p1, p2};
        }
    }
    ans+=cnt;
    if(k==1){
        sort(base, base+2*cnt);
        forn(i, cnt) ans-=base[i];
        forsn(i, cnt, 2*cnt) ans+=base[i];
        printf("%lld\n", ans);
    }
    if(k==2){
        sort(arr, arr+cnt, [](pii a, pii b){
            return (a.F+a.S) < (b.F+b.S);
        });
        med aa, bb;
        forn(i, cnt){
            aa.insert({arr[i].F, 2*i});
            aa.insert({arr[i].S, 2*i+1});
            res[0][i+1]=aa.calc();
        }
        dforn(i, cnt){
            bb.insert({arr[i].F, 2*i});
            bb.insert({arr[i].S, 2*i+1});
            res[1][i]=bb.calc();
        }
        ll mn=INF;
        forn(i, cnt+1) mn=min(mn, res[0][i]+res[1][i]);
        ans+=mn;
        printf("%lld\n", ans);
    }
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d %d", &k, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf(" %c %d %c %d", &c1, &p1, &c2, &p2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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