Submission #565432

#	Time	Username	Problem	Language	Result	Execution time	Memory
565432		four_specks	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	53 ms	2512 KiB

bridge

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

inline namespace
{
    template <typename T, typename Cmp = less<T>>
    using OrderedSet = tree<T, null_type, Cmp, rb_tree_tag, tree_order_statistics_node_update>;

    template <typename T = int>
    struct PURS
    {
        PURS(int _n) : n(_n), tree(n + 1, 0) {}

        PURS(const vector<T> &vec)
            : PURS((int)vec.size())
        {
            for (int i = 0; i < n; i++)
                add(i, vec[i]);
        }

        void add(int k, T x)
        {
            for (int p = k + 1; p <= n; p += p & -p)
                tree[p] += x;
        }

        T sum(int l = 0) const { return sum(l, n); }
        T sum(int l, int r) const { return acc(r) - acc(l); }

        T get(int k) const { return sum(k, k + 1); }
        void set(int k, T x) { add(k, x - get(k)); }

        int size() const { return n; }

    private:
        int n;
        vector<T> tree;

        T acc(int k) const
        {
            T ret = 0;
            for (int p = k; p; p -= p & -p)
                ret += tree[p];

            return ret;
        }
    };

} // namespace

void solve()
{
    int n, k;
    cin >> k >> n;

    if (k == 1)
    {
        vector<long> x;

        long add = 0;
        for (int i = 0; i < n; i++)
        {
            char p, q;
            long s, t;
            cin >> p >> s >> q >> t;

            if (p == q)
                add += abs(s - t);
            else
                add += 1,
                x.push_back(s),
                x.push_back(t);
        }
        sort(x.begin(), x.end());

        int m = (int)x.size();

        long u = x[(m - 1) / 2];

        long sum = add;
        for (long s : x)
            sum += abs(u - s);

        cout << sum << '\n';
    }
    else
    {

        long add = 0;

        vector<long> vals;

        vector<array<long, 2>> u;
        for (int i = 0; i < n; i++)
        {
            char p, q;
            long s, t;
            cin >> p >> s >> q >> t;

            if (s < t)
                swap(s, t);

            if (p == q)
                add += s - t;
            else
            {
                u.push_back({s, t});

                vals.push_back(s),
                vals.push_back(t);

                add += 1;
            }
        }
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());

        int z = (int)vals.size();

        auto idx = [&](long x) -> int
        { return (int)(lower_bound(vals.begin(), vals.end(), x) - vals.begin()); };

        int m = (int)u.size();

        sort(
        u.begin(), u.end(),
        [&](const auto &lhs, const auto &rhs) -> bool
        { return lhs[0] + lhs[1] < rhs[0] + rhs[1]; });

        vector<long> pref(m + 1), suff(m + 1);
        pref[0] = suff[m] = 0;
        {
            PURS<long> purs(z);
            OrderedSet<pair<int, int>> oset;
            for (int i = 0; i < m; i++)
            {
                for (long x : u[i])
                {
                    int l = idx(x);
                    purs.add(l, x);
                    oset.insert(pair(l, i));
                }
                int d = ((int)oset.size()) / 2, j = oset.find_by_order(d)->first;
                pref[i + 1] = purs.sum(j) - purs.sum(0, j);
            }
        }
        {
            PURS<long> purs(z);
            OrderedSet<pair<int, int>> oset;
            for (int i = m - 1; i >= 0; i--)
            {
                for (int x : u[i])
                {
                    int l = idx(x);
                    purs.add(l, x);
                    oset.insert(pair(l, i));
                }
                int d = ((int)oset.size()) / 2, j = oset.find_by_order(d)->first;
                suff[i] = purs.sum(j) - purs.sum(0, j);
            }
        }

        long res = LONG_MAX;
        for (int i = 0; i <= m; i++)
            res = min(res, pref[i] + suff[i]);

        cout << res + add << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

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