Submission #232470

#	Time	Username	Problem	Language	Result	Execution time	Memory
232470		balbit	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2069 ms	12900 KiB

bridge

#include <bits/stdc++.h>
#define ll long long
using namespace std;

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" - ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()

#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#endif // BALBIT

#define pii pair<ll, ll>
#define f first
#define s second

#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x.size())
#define pb push_back

vector<pii> v;
int n;

ll C(ll l, ll r) {
    if (l>r) swap(l,r);
    ll re = 0;
    for (pii & p : v) {
        if (p.s < l) re += l-p.s;
        else if (p.f > r) re += p.f-r;
        else if (p.f>l && p.s < r) re += min (p.f-l, r-p.s);
    }
    return re;
}

ll RE;
vector<int> p;
int m;

void go(int il, int ir, int jl, int jr) {
    if (il > ir || jl > jr) return;
    int mid = (il + ir)/2;
    int best = -1;
    ll bestval = 2e18+3;

    for (int j = jl; j<=jr; ++j) {
        ll tt = C(p[mid], p[j]);
        RE = min (RE, tt);
        if (tt < bestval) {
            best = j; bestval = tt;
        }
    }
    go(il, mid-1, jl, best);
    go(mid+1, ir, best, jr);

}

signed main(){
    IOS();
    int k; cin>>k>>n;
    ll re = 0;
    map<int, int> hv;
    for (int i = 0; i<n; ++i) {
        char x, x2;
        int l, r; cin>>x>>l>>x2>>r;
        re += abs(r-l);
        if (x == x2) {
        }else{
            if (r < l) swap(l,r);
            v.pb({l,r});
            hv[l]--;
            hv[r]--;
        }
    }
    n = SZ(v);

    if (k == 1) {
        ll now = C(0,0);
        bug(now);
        ll ans = now;
        ll x = 0;
        ll frt = n;
        for (pii ele : hv) {
            ll X = ele.f;
            now -= (X-x) * (frt);
            bug(X, now);
            ans = min(ans, now);
            frt += ele.s;
            x=X;
        }
        cout<<re + ans*2 + n<<endl;
    }else{
         m = SZ(hv);
         p.resize(m);
         RE = C(0,0);

        int _it = 0;
        for (pii ele : hv) {
            p[_it++] = ele.f;
        }
        go(0,m-1,0,m-1);
//        cout<<re + ans*2 + n<<endl;
        cout<<re + RE*2 + n<<endl;
    }

}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

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