Submission #651789

#	Time	Username	Problem	Language	Result	Execution time	Memory
651789		HaYoungJoon	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	246 ms	13452 KiB

bridge

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second

using namespace std;

typedef pair<ll,ll> pii;
typedef pair<pii,pii> piiii;
const int maxn = 2e5 + 1;
int n,k, cnt[4*maxn];
ll bit[maxn];
pii a[maxn];

struct IT {
    void update(int v, int tl, int tr, int pos, int w) {
        if (tl == tr) {
            cnt[v] += w;
            return;
        }
        int tm = (tl + tr)/2;
        if (pos <= tm) update(2*v,tl,tm,pos,w);
        else update(2*v+1,tm+1,tr,pos,w);
        cnt[v] = cnt[2*v] + cnt[2*v+1];
    }
    int getMedian(int v, int tl, int tr, int w) {
        if (tl == tr) return tl;
        int tm = (tl + tr)/2;
        if (cnt[2*v] >= w) return getMedian(2*v,tl,tm,w);
        else return getMedian(2*v+1,tm+1,tr,w - cnt[2*v]);
    }
} seg;

struct BIT {
    void update(int idx, ll val, int m) {
        for (; idx <= m; idx += (idx & -idx)) bit[idx] += val;
    }
    ll getSum(int L, int R) {
        if (L > R) return 0;
        L--;
        ll res = 0;
        for (; L > 0; L -= (L & -L)) res -= bit[L];
        for (; R > 0; R -= (R & -R)) res += bit[R];
        return res;
    }
} fen;

void solve1() {
    vector<ll> arr;
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        char C1,C2;
        ll x,y;
        cin >> C1 >> x >> C2 >> y;
        if (C1 == C2) res += abs(x-y);
        else {
            arr.push_back(x);
            arr.push_back(y);
            res++;
        }
    }
    sort(arr.begin(),arr.end());
    ll mid = arr[arr.size()/2];
    for (ll x: arr) res += abs(mid-x);
    cout << res;
}

bool cmp(piiii A, piiii B) {
    return A.fi.fi + A.fi.se < B.fi.fi + B.fi.se;
}

ll sum[maxn];

void solve2() {
    vector<piiii> arr;
    vector<pii> roirac;
    ll same = 0;
    for (int i = 1; i <= n; i++) {
        char C1,C2;
        ll x,y;
        cin >> C1 >> x >> C2 >> y;
        if (C1 == C2) same += abs(x-y);
        else {
            arr.push_back(piiii(pii(x,y),pii(0,0)));
            same++;
        }
    }
    sort(arr.begin(),arr.end(),cmp);
    int m = arr.size();
    for (int i = 0; i < m; i++) {
        roirac.push_back(pii(arr[i].fi.fi,i+1));
        roirac.push_back(pii(arr[i].fi.se,i+1 + m));
    }
    sort(roirac.begin(),roirac.end());
    for (int i = 0; i < m; i++) {
        arr[i].se.fi = lower_bound(roirac.begin(),roirac.end(),pii(arr[i].fi.fi,i+1)) - roirac.begin() + 1;
        arr[i].se.se = lower_bound(roirac.begin(),roirac.end(),pii(arr[i].fi.se,i+1 + m)) - roirac.begin() + 1;
    }

    for (int i = 0; i < m; i++) {
        seg.update(1,1,2*m,arr[i].se.fi,1);
        fen.update(arr[i].se.fi,arr[i].fi.fi,2*m);
        seg.update(1,1,2*m,arr[i].se.se,1);
        fen.update(arr[i].se.se,arr[i].fi.se,2*m);
        int mid = seg.getMedian(1,1,2*m,(2*(i+1) + 1)/2);
        sum[i+1] = fen.getSum(mid+1,2*m) - fen.getSum(1,mid);
    }
    for (int i = 0; i < m; i++) {
        seg.update(1,1,2*m,arr[i].se.fi,-1);
        fen.update(arr[i].se.fi,-arr[i].fi.fi,2*m);
        seg.update(1,1,2*m,arr[i].se.se,-1);
        fen.update(arr[i].se.se,-arr[i].fi.se,2*m);
    }
    for (int i = m-1; i >= 0; i--) {
        seg.update(1,1,2*m,arr[i].se.fi,1);
        fen.update(arr[i].se.fi,arr[i].fi.fi,2*m);
        seg.update(1,1,2*m,arr[i].se.se,1);
        fen.update(arr[i].se.se,arr[i].fi.se,2*m);
        int mid = seg.getMedian(1,1,2*m,(2*(m-i)+1)/2);
        sum[i] += fen.getSum(mid+1,2*m) - fen.getSum(1,mid);
    }
    ll bridge = 1e18;
    for (int i = 0; i <= m; i++) bridge = min(bridge,sum[i]);
    cout << same + bridge;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int type;
    cin >> type >> n;
    if (type == 1) solve1();
    else solve2();
    return 0;
}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

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