Submission #257475

#	Time	Username	Problem	Language	Result	Execution time	Memory
257475		evpipis	Palembang Bridges (APIO15_bridge)	C++11	49 / 100	2093 ms	38572 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 = 2e5, mx_ts = 1e9;
vector<ii> vec;
vector<int> cord, hel;
ll pref[len], suf[len];
map<int, int> mym;

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, int v){
    pnode cur = t;
    if (cur == null)
        cur = new node(0, 0, null, null);
    cur->num++;
    cur->sum += v;

    if (l == r)
        return cur;

    int mid = (l+r)/2;
    if (i <= mid)
        cur->lef = add(t->lef, l, mid, i, v);
    else
        cur->rig = add(t->rig, mid+1, r, i, v);
    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, mym[pos], mx);
    pil rig = ask(root_rig, 0, mx, 0, mym[pos]);

    //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);
}

ll ts(){
    int l = -1, r = (int)hel.size()-1;
    while (l+1 < r){
        int mid = (l+r)/2;
        if (func(hel[mid]) < func(hel[mid+1]))
            r = mid;
        else
            l = mid;
    }

    return func(hel[l+1]);
}

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);

    for (int i = 0; i < m; i++){
        int a = vec[i].fi, b = vec[i].se;
        cord.pb(a), cord.pb(b);
    }

    sort(cord.begin(), cord.end());

    int cnt = 0;
    for (int i = 0; i < cord.size(); i++)
        if (i == 0 || cord[i] != cord[i-1])
            hel.pb(cord[i]), mym[cord[i]] = cnt++;

    //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, mym[a], a);
        root_rig = add(root_rig, 0, mx, mym[b], b);

        pref[i] = ts();
    }

    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, mym[a], a);
        root_rig = add(root_rig, 0, mx, mym[b], b);

        suf[i] = ts();
    }

    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:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < cord.size(); i++)
                     ~~^~~~~~~~~~~~~
bridge.cpp:93: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:97: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