Submission #1124223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124223		kfhjad	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	549 ms	23936 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, 6, 0, 1, 0, 1, 0};

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

    // std::cout << "lowerbound: " << fenwick.lowerbound(9) << 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, i] : comp)
    {
        i = 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 = decomp[med] * f.query(med) - fsum.query(med);
        ll rside = fsum.query(2 * n) - fsum.query(med) - (decomp[med] * (i * 2 - f.query(med)));
        
        // cout << "f: " << f.query(med) << ' ' << fsum.query(med) << endl;
        // cout << lside << ' ' << rside << endl;

        prefix[i] = lside + rside;
    }
    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 = decomp[med] * f.query(med) - fsum.query(med);
            ll rside = fsum.query(2 * n) - fsum.query(med) - (decomp[med] * ((n - i + 1) * 2 - f.query(med)));
            
            // cout << lside << ' ' << rside << endl;

            ans = std::min(ans, prefix[i - 1] + lside + rside);
        }
    }
    
    // cout << prefix[1] << endl;
    
    // cout << n << ' ' << extra << ' ' << prefix[n] << endl;

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

    return 0;
}

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