Submission #1138916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138916		buzdi	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	0 ms	328 KiB

bridge

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define ll long long
#define ld long double

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int NMAX = 2e5;
const ll INF = 1e18;

struct AIB {
    int n;
    int log_n;
    ll aib[2 * NMAX + 1];

    void Initialize(int n) {
        this->n = n;
        log_n = 0;
        while((1 << (log_n + 1)) <= n) {
            log_n++;
        }
        for(int i = 1; i <= n; i++) {
            aib[i] = 0;
        }
    }

    void Update(int pos, ll value) {
        for(int i = pos; i <= n; i += i & (-i)) {
            aib[i] += value;
        }
    }

    ll Query(int pos) {
        ll answer = 0;
        for(int i = pos; i >= 1; i -= i & (-i)) {
            answer += aib[i];
        }
        return answer;
    }

    int GetValue(int k) {
        int pos = 0;
        int sum = 0;
        for(int i = log_n; i >= 0; i--) {
            if(pos + (1 << i) <= n && sum + aib[pos + (1 << i)] < k) {
                sum += aib[pos + (1 << i)];
                pos += (1 << i);
            }
        }
        return pos + 1;
    }
}aib_freq, aib_sum;

int k, n, ind, ID;
ll answer;
pair<int, int> houses[NMAX + 1];
int a[2 * NMAX + 1];
ll min_left[NMAX + 1];
ll min_right[NMAX + 2];
map<int, int> mp;

void Update(int x, int y) {
    aib_freq.Update(mp[x], 1);
    aib_freq.Update(mp[y], 1);

    aib_sum.Update(mp[x], x);
    aib_sum.Update(mp[y], y);    
}

ll GetMinDistance(int n) {
    int median = aib_freq.GetValue(n / 2 + 1); 
    int real_median = mp[median];
    int smaller_equal = aib_freq.Query(median);
    int greater = n - smaller_equal;
    ll sum_smaller_equal = aib_sum.Query(median);
    ll sum_greater = aib_sum.Query(ID) - sum_smaller_equal;
    ll min_distance = (ll) real_median * smaller_equal - sum_smaller_equal + sum_greater - (ll) real_median * greater;    
    return min_distance;
}

void Solve1() {
    for(int i = 1; i <= n; i++) {
        a[++ind] = houses[i].first;
        a[++ind] = houses[i].second;
    }

    sort(a + 1, a + ind + 1);
    for(int i = 1; i <= ind; i++) {
        answer += abs(a[i] - a[ind / 2 + 1]);
    }
    cout << answer << '\n';
    answer += n;
    cout << answer << '\n';
}

void Solve2() {
    for(int i = 1; i <= n; i++) {
        mp[houses[i].first] = 1;
        mp[houses[i].second] = 1;
    }

    for(auto &x : mp) {
        x.second = ++ID;
    }

    aib_sum.Initialize(ID);
    aib_freq.Initialize(ID);
    for(int i = 1; i <= n; i++) {
        Update(houses[i].first, houses[i].second);
        min_left[i] = GetMinDistance(2 * i);
    }

    aib_sum.Initialize(ID);
    aib_freq.Initialize(ID);
    min_right[n + 1] = INF;
    for(int i = n; i >= 1; i--) {
        Update(houses[i].first, houses[i].second);
        min_right[i] = GetMinDistance(2 * (n - i + 1));
    } 

    // for(int i = 1; i <= n; i++) {
    //     cout << min_left[i] << ' ';
    // }
    // cout << '\n';

    ll answer_bridge = INF;
    for(int i = 1; i < n; i++) {
        answer_bridge = min(answer_bridge, min_left[i] + min_right[i + 1]);
    }
    answer += answer_bridge;
    answer += n;
    cout << answer << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> k >> n;
    for(int i = 1; i <= n; i++) {
        char z1, z2;
        int x, y;
        cin >> z1 >> x >> z2 >> y;
        if(z1 != z2) {
            houses[++ind] = {x, y};
        }
        else {
            answer += abs(x - y);
        }
    }
    n = ind;
    ind = 0;

    if(k == 1) {
        Solve1();
    }
    else {
        Solve2();
    }

    return 0;
}

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