Submission #1124213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124213		kfhjad	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	1 ms	328 KiB

bridge

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Fenwick
{
    int n;
    std::vector<ll> f;

    Fenwick(int nn = 0)
    {
        init(nn);
    }

    void init(int n_)
    {
        n = n_;
        f.assign(n + 1, 0);
    }

    void update(int i, int x)
    {
        for (; i <= n; i += i & -i)
            f[i] += x;
    }

    ll query(int i)
    {
        ll ans = 0;
        for (; i > 0; i -= i & -i)
            ans += f[i];

        return ans;
    }

    int lowerbound(ll sum)
    {
        int pos = 0;

        for (int i = 1 << 25; i > 0; i /= 2)
            if (pos + i <= n && f[pos + i] < sum)
                pos += i, sum -= f[pos];

        return pos + 1;
    }
};

int main()
{
    std::cin.tie(NULL)->std::ios::sync_with_stdio(false);

    int k, n;
    std::cin >> k >> n;

    ll extra = 0;
    std::vector<std::pair<int, int>> v;
    std::map<int, int> comp, decomp;

    // Fenwick fenwick(100);

    // std::vector<int> a = {1, 0, 1, 0, 1, 0, 1, 0, 1, 0};

    // for (int i = 0; i < 10; ++i)
    // {
    //     fenwick.update(i + 1, a[i]);
    // }

    // std::cout << fenwick.lowerbound(0) << std::endl;

    for (int i = 0; i < n; ++i)
    {
        char z1, z2;
        int a, b;
        std::cin >> z1 >> a >> z2 >> b;

        if (z1 == z2)
            extra += std::abs(b - a);
        else
            v.push_back({a, b}), comp[a], comp[b];
    }

    n = v.size();

    int cnt = 1;
    for (auto &[x, _] : comp)
    {
        comp[x] = cnt;
        decomp[cnt++] = x;
    }

    std::sort(v.begin(), v.end(), [](auto &a, auto &b)
              { return a.first + a.second < b.first + b.second; });

    std::vector<ll> prefix(n + 1);
    Fenwick f(2 * n), fsum(2 * n);

    for (int i = 1; i <= n; ++i)
    {
        auto [l, r] = v[i - 1];
        f.update(comp[l], 1);
        f.update(comp[r], 1);
        fsum.update(comp[l], l);
        fsum.update(comp[r], r);

        ll med = f.lowerbound(i);

        ll lside = fsum.query(med);
        ll rside = fsum.query(2 * n) - lside;

        prefix[i] = i * (decomp[med]) - lside + rside - i * (decomp[med]);
    }
    ll ans = prefix[n];

    if (k == 2)
    {
        f.init(2 * n);
        fsum.init(2 * n);
        for (int i = n; i > 0; --i)
        {
            auto [l, r] = v[i - 1];
            f.update(comp[l], 1);
            f.update(comp[r], 1);
            fsum.update(comp[l], l);
            fsum.update(comp[r], r);

            ll med = f.lowerbound(n - i + 1);

            ll lside = fsum.query(med);
            ll rside = fsum.query(2 * n) - lside;

            ans = std::min(ans, prefix[i - 1] + i * (decomp[med]) - lside + rside - i * (decomp[med]));
        }
    }

    std::cout << n + extra + ans << '\n';

    return 0;
}

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