Submission #826804

#	Time	Username	Problem	Language	Result	Execution time	Memory
826804		rinho	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	340 KiB

bridge

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

const int Nmax = 2e5;
const int MOD = 1000000007;

struct SegmentTree{
    int st[Nmax * 4 + 3];

    void update(int id, int l, int r, int i, int v){
        if(i < l || i > r) return;
        if(l == r){
            st[id] += v;
            return;
        }
        int mid = (l + r) / 2;

        update(id * 2, l, mid, i, v);
        update(id * 2 + 1, mid + 1, r, i, v);

        st[id] = st[id * 2] + st[id * 2 + 1];
    }

    int get(int id, int l, int r, int k){
        if(l == r) return l;
        int mid = (l + r) / 2;
        if(k <= st[id * 2]){
            return get(id * 2, l, mid, k);
        }
        return get(id * 2 + 1, mid + 1, r, k - st[id * 2]);
    }
} segtree;

int n, k, sz = 0, period = 0;
pair<pair<int, int>, pair<int, int>> a[Nmax + 3];
vector<int> value;
int is[Nmax + 3];
long long ans = 0;

bool cmp(pair<pair<int, int>, pair<int, int>> x, pair<pair<int, int>, pair<int, int>> y){
    if(x.second.second == y.second.second) return x.second.first < y.second.first;
    return x.second.second < y.second.second;
}

void in(){
    cin >> k >> n;
    for(int i = 1; i <= n; i++) {
        char p, q;
        int s, t;
        cin >> p >> s >> q >> t;
        if(p == q){
            ans += 0ll + t - s;
            continue;
        }
        sz++;
        a[sz].first.first = (s + t) / 2;
        a[sz].first.second = a[sz].first.first;
        a[sz].second.first = s;
        a[sz].second.second = t;
        value.push_back(a[sz].first.first);
    }
    sort(value.begin(), value.end());
    value.erase(unique(value.begin(), value.end()), value.end());

    for(int i = 1; i <= sz; i++){
        a[i].first.first = lower_bound(value.begin(), value.end(), a[i].first.first) - value.begin() + 1;
        period = max(period, a[i].first.first);
        is[a[i].first.first] = a[i].first.second;
    }

    sort(a + 1, a + sz + 1, cmp);
}

void setto(int l, int r, int v){
    for(int i = l; i <= r; i++){
        segtree.update(1, 1, period, a[i].first.first, v);
    }
}

long long calc(int mid){
    long long res = 0;
    setto(1, mid, 1);

    int med1 = is[segtree.get(1, 1, period, (mid + 1) / 2)];

    for(int i = 1; i <= mid; i++){
        res += 0ll + abs(a[i].second.first - med1) + abs(a[i].second.second - med1);
    }
    setto(1, mid, -1);

    setto(mid + 1, sz, 1);

    int med2 = is[segtree.get(1, 1, period, (sz - mid + 1) / 2)];

    for(int i = mid + 1; i <= sz; i++){
        res += 0ll + abs(a[i].second.first - med2) + abs(a[i].second.second - med2);
    }
    setto(mid + 1, sz, -1);
    return res;
}

void sol(){
    if(k == 1){
        // setto(1, sz, 1);

        // int med = is[segtree.get(1, 1, period, (sz + 1) / 2)];

        // for(int i = 1; i <= sz; i++){
        //     ans += 0ll + abs(a[i].second.first - med) + abs(a[i].second.second - med);
        // }
    } else {
        long long res = 1e18;
        for(int i = 1; i < sz; i++){
            res = min(res, calc(i));
        }
        ans += 0ll + res;
    }
    cout << 0ll + ans + sz;
}
int main(){
    //freopen(" ", "r", stdin);
    //freopen(" ", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
       in();
       sol();
    }
    return 0;
}

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