Submission #257486

#	Time	Username	Problem	Language	Result	Execution time	Memory
257486		evpipis	Palembang Bridges (APIO15_bridge)	C++11	100 / 100	1713 ms	20140 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 bit{
    pil tree[mx+4];
    int rev;

    bit(int r = 0){
        rev = r;
    }

    void init(){
        for (int i = 1; i <= mx; i++)
            tree[i] = mp(0, 0);
    }

    void add(int i, int v){
        if (rev)
            i = mx-i+1;

        while (i <= mx)
            tree[i].fi++, tree[i].se += v, i += i&(-i);
    }

    pil ask(int i){
        if (rev)
            i = mx-i+1;

        pil ans = mp(0, 0);
        while (i > 0)
            ans.fi += tree[i].fi, ans.se += tree[i].se, i -= i&(-i);
        return ans;
    }
};

bit lef = bit(1), rig = bit(0);

ll func(int pos){
    pil le = lef.ask(mym[pos]);
    pil ri = rig.ask(mym[pos]);

    return (le.se - pos*1LL*le.fi) + (pos*1LL*ri.fi - ri.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;

    lef.init(), rig.init();
    for (int i = 0; i < m; i++){
        int a = vec[i].fi, b = vec[i].se;
        lef.add(mym[a], a);
        rig.add(mym[b], b);

        pref[i] = ts();
    }

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

    lef.init(), rig.init();
    for (int i = m-1; i >= 0; i--){
        int a = vec[i].fi, b = vec[i].se;
        lef.add(mym[a], a);
        rig.add(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("%lld\n", 2*ans+sum);
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < cord.size(); i++)
                     ~~^~~~~~~~~~~~~
bridge.cpp:79: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:83: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: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37