Submission #249765

#	Time	Username	Problem	Language	Result	Execution time	Memory
249765		rdd6584	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	91 ms	7424 KiB

bridge

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

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const ll MOD = (ll)1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;

ll fac[1] = {1}, inv[1] = {1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll mp(ll a,ll b){ll ret=1;while(b){if(b&1)ret=ret*a%MOD;a=a*a%MOD;b>>=1;}return ret;}
ll cmb(ll r, ll c) {return fac[r] * inv[c] % MOD * inv[r - c] % MOD;}

vector<pll> v;
vector<int> cc;

ll cal(int mid) {
    ll ret= 0;
    for (pll i : v) {
        if (i.first <= mid && mid <= i.second) ret += (i.second-i.first);
        else ret += abs(i.first-mid) + abs(i.second-mid);
    }
    return ret;
}

int n;
vector<ll> x;
int szz = 200000;

struct pen {
    ll tree[200001];
    void upd(int i, ll val) {
        for (; i <= szz; i+=i&-i) tree[i]+=val;
    }
    ll find(int i) {
        ll ret = 0;
        for (; i; i-= i&-i) ret += tree[i];
        return ret;
    }
} lsum, lro, rsum, rro;

ll lp[100001];
ll rp[100001];

ll gg(ll mid) {
    int t = lower_bound(all(x), mid) - x.begin();
    ll ret = 0;
    ret += lro.find(t)*mid - lsum.find(t);
   //  printf("/// %lld : %lld\n", mid, ret );

    ret += (rsum.find(200000) - rsum.find(t)) - (rro.find(200000) - rro.find(t))*mid;

   //  printf("/// %lld : %lld\n", mid, ret );

    ret += rro.find(t)*mid - rsum.find(t);
    ret += (lsum.find(200000) - lsum.find(t)) - (lro.find(200000) - lro.find(t))*mid;
   //  printf("/// %lld : %lld\n", mid, ret );

    return ret;
}

int main() {
    int k;
    scanf("%d %d", &k, &n);

    ll sum = 0;
    for (int i = 0; i < n; i++) {
        char a,c;
        int b,d;
        scanf(" %c %d %c %d", &a, &b ,&c, &d);
        if (a!=c) {
            if (b>d) swap(b,d);
            sum++;
            v.push_back({b, d});
            x.push_back(b);
            x.push_back(d);
        }
        else sum += abs(b-d);
    }
    x.push_back(-1);
    sort(all(x));
    x.erase(unique(all(x)), x.end());

    if (k==1) {
        for (pll i : v) cc.push_back(i.first), cc.push_back(i.second);
        sort(all(cc));
        if (cc.empty()) printf("%lld\n", sum);
        else printf("%lld", cal(cc[sz(cc)/2])+sum);
        return 0;
    }

    sort(all(v), [](pll a, pll b){return a.first+a.second < b.first+b.second;});

    multiset<ll> se;
    auto med = se.begin();
    for (int cnt = 0; cnt < 2; cnt++) {
        se.clear();
        if (cnt==1) {
            memcpy(rp, lp, sizeof(lp));
            reverse(all(v));
            memset(lsum.tree, 0, sizeof(ll)*(szz+1));
            memset(rsum.tree, 0, sizeof(ll)*(szz+1));

            memset(lro.tree, 0, sizeof(ll)*(szz+1));
            memset(rro.tree, 0, sizeof(ll)*(szz+1));
        }

        for (int i = 0; i < sz(v); i++) {
            int lt = lower_bound(all(x), v[i].first) - x.begin();
            lsum.upd(lt, v[i].first);
            lro.upd(lt, 1);

            int rt = lower_bound(all(x), v[i].second) - x.begin();
            rsum.upd(rt, v[i].second);
            rro.upd(rt, 1);


            if (se.empty()) se.insert(v[i].first), med = se.begin();
            else {
                se.insert(v[i].first);
                if (sz(se) % 2 && *med < v[i].first) med++;
                else if (sz(se) % 2 == 0 && *med >= v[i].first) med--;
            }

            se.insert(v[i].second);
            if (sz(se) % 2 && *med < v[i].second) med++;
            else if (sz(se) % 2 == 0 && *med >= v[i].second) med--;


            int le = 0, ri = sz(x) - 1, mid;
            while (le<=ri) {
                mid = (le+ri)/2;
                int t = lro.find(mid) + rro.find(mid);
                if (t >= i+1) ri = mid - 1;
                else le = mid + 1;
            }

            // assert(x[le] == *med);
            // printf("%lld %lld\n", x[le], *med);
            lp[i] = gg(x[le]);
            // printf("%d : %lld %lld / %lld %lld \n", i, v[i].first, v[i].second, lp[i], *med);
        }
    }

    ll ans = 9e18;
    for (int i = 0; i < sz(v) - 1; i++) {
        ans = min(ans, lp[i] + rp[sz(v) - i - 2]);
        // printf("%d : %d : %lld %lld\n", sz(v) - i - 2, i, rp[sz(v)-i-2], lp[i]);
    }
    printf("%lld", sum+ans);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &k, &n);
     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %c %d", &a, &b ,&c, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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