Submission #257473

#	Time	Username	Problem	Language	Result	Execution time	Memory
257473		evpipis	Palembang Bridges (APIO15_bridge)	C++11	49 / 100	2080 ms	4472 KiB

bridge

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
typedef pair<int, ll> pil;

const int len = 1e5+5, mx = 1e9;
vector<ii> vec;
ll pref[len], suf[len];

struct node{
    int num;
    ll sum;
    node *lef, *rig;

    node(int n = 0, ll s = 0, node *l = NULL, node *r = NULL){
        num = n;
        sum = s;
        lef = l;
        rig = r;
    }
};

typedef node* pnode;
pnode null = new node(), root_lef, root_rig;

pnode add(pnode t, int l, int r, int i){
    pnode cur = t;
    if (cur == null)
        cur = new node(0, 0, null, null);
    cur->num++;
    cur->sum += i;

    if (l == r)
        return cur;

    int mid = (l+r)/2;
    if (i <= mid)
        cur->lef = add(t->lef, l, mid, i);
    else
        cur->rig = add(t->rig, mid+1, r, i);
    return cur;
}

pil ask(pnode t, int l, int r, int i, int j){
    if (r < i || j < l)
        return mp(0, 0);
    if (i <= l && r <= j)
        return mp(t->num, t->sum);

    int mid = (l+r)/2;
    pil lef = ask(t->lef, l, mid, i, j);
    pil rig = ask(t->rig, mid+1, r, i, j);
    return mp(lef.fi+rig.fi, lef.se+rig.se);
}

ll func(int pos){
    pil lef = ask(root_lef, 0, mx, pos+1, mx);
    pil rig = ask(root_rig, 0, mx, 0, pos-1);

    //printf("func(%d) = %lld\n", pos, (lef.se - pos*1LL*lef.fi) + (pos*1LL*rig.fi - rig.se));

    return (lef.se - pos*1LL*lef.fi) + (pos*1LL*rig.fi - rig.se);
}

bool comp(ii a, ii b){
    return (a.fi+a.se < b.fi+b.se);
}

int main(){
    int k, n;
    ll sum = 0;
    scanf("%d %d", &k, &n);
    for (int i = 0; i < n; i++){
        char tpa, tpb;
        int a, b;
        scanf(" %c %d %c %d", &tpa, &a, &tpb, &b);

        if (a > b)
            swap(a, b);
        sum += b-a;

        if (tpa != tpb)
            vec.pb(mp(a, b)), sum++;
    }

    int m = vec.size();
    sort(vec.begin(), vec.end(), comp);

    //printf("after sort:\n");
    //for (int i = 0; i < m; i++)
      //  printf("(%d, %d)\n", vec[i].fi, vec[i].se);

    null->lef = null->rig = null;

    root_lef = root_rig = null;
    for (int i = 0; i < m; i++){
        //printf("building pref: i = %d\n", i);
        int a = vec[i].fi, b = vec[i].se;
        root_lef = add(root_lef, 0, mx, a);
        root_rig = add(root_rig, 0, mx, b);

        int l = -1, r = mx;
        while (l+1 < r){
            int mid = (l+r)/2;
            if (func(mid) < func(mid+1))
                r = mid;
            else
                l = mid;
        }

        pref[i] = func(l+1);
    }

    if (k == 1){
        printf("%lld\n", sum+2*pref[m-1]);
        return 0;
    }

    root_lef = root_rig = null;
    for (int i = m-1; i >= 0; i--){
        int a = vec[i].fi, b = vec[i].se;
        root_lef = add(root_lef, 0, mx, a);
        root_rig = add(root_rig, 0, mx, b);

        int l = -1, r = mx;
        while (l+1 < r){
            int mid = (l+r)/2;
            if (func(mid) < func(mid+1))
                r = mid;
            else
                l = mid;
        }

        suf[i] = func(l+1);
    }

    ll ans = pref[m-1];
    for (int i = 0; i+1 < m; i++)
        ans = min(ans, pref[i]+suf[i+1]);

    //printf("ans = %lld, sum = %lld\n", ans, sum);
    printf("%lld\n", 2*ans+sum);
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:78: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:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %c %d", &tpa, &a, &tpb, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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