Submission #348968

#	Time	Username	Problem	Language	Result	Execution time	Memory
348968		shivensinha4	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	412 ms	23144 KiB

bridge

#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'

// Ask for sum 1 -> n for full (one based indexing)
class BIT {
private: vector<ll> ct; int n;
    int LSOne(int x) {
        return x&(-x);
    }

public:
    BIT(int x) {
        n = x;
        ct.resize(n+1);
    }
    ll sum(int a) {
        ll sum = 0;
        for (; a > 0; a -= LSOne(a)) sum += ct[a];
        return sum;
    }
    ll sum(int a, int b) {
        return sum(b) - (a == 1 ? 0 : sum(a-1));
    }
    void update(int p, ll v) {
        for (; p < n+1; p += LSOne(p)) ct[p] += v;
    }
};



int main() {
#ifdef mlocal
    freopen("test.in", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int k, n; cin >> k >> n;
    ll init = 0;
    vector<vector<ll>> pts; // {point; -1 -> start, 1 -> end; other end point}
    vector<ii> seg;
    map<int, int> ptToId;
    vector<ll> idToPt(1);

    for_(i, 0, n) {
        char za, zb; int a, b; cin >> za >> a >> zb >> b;
        a += 1, b += 1;
        if (b < a) {
            swap(za, zb);
            swap(a, b);
        }
        if (za != zb) {
            seg.push_back({a, b});
            ptToId[a] = ptToId[b] = 0;
            init++;
        } else init += b-a;
    }

    int pt = 1;

    for (auto i: ptToId) {
        ptToId[i.first] = pt++;
        idToPt.push_back(i.first);
    }

    for (auto i: seg) {
        pts.push_back({ptToId[i.first], -1, ptToId[i.second]});
        pts.push_back({ptToId[i.second], 1, ptToId[i.first]});
    }

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

    if (k == 1) {
        for (auto i: pts) init += abs(idToPt[i[0]]-idToPt[pts[pts.size()/2][0]]);
        cout << init << endl;
        return 0;
    }

    BIT sum(pt+1), ct(pt+1);
    for (auto i: pts) {
        ct.update(i[0], 1);
        sum.update(i[0], idToPt[i[0]]);
    }

    ll mn = LONG_LONG_MAX;
    ll curr = 0;
    for (auto i: pts) {
//        for (int j: i) cout << j << " ";
//        cout << endl;
        ct.update(i[0], i[1]);
        ct.update(i[2], i[1]);
        sum.update(i[0], i[1]*idToPt[i[0]]);
        sum.update(i[2], i[1]*idToPt[i[2]]);
        curr += (-i[1]) * abs(idToPt[i[0]]-idToPt[i[2]]);

        if (i[1] == -1) {
            int l = 1, r = pt+1, ans = -1;
            while (l < r) {
                int mid = (l+r)/2;
                ll ls = ct.sum(mid), rs = ct.sum(mid+1, pt);
                if (ls >= rs) {
                    ans = r = mid;
                } else l = mid+1;
            }

//            cout << ans << " " << curr << endl;
//            cout << "left : " << ct.sum(ans) << " right: " << ct.sum(ans+1, pt+1) << endl;
            mn = min(mn, idToPt[ans]*(ct.sum(ans)-ct.sum(ans+1, pt)) - sum.sum(ans) + sum.sum(ans+1, pt) + curr);
        }
    }

    cout << init+mn << endl;


    return 0;
}

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