제출 #565954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
565954		four_specks	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	484 ms	21424 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;

    long res = 0;
    if (k == 1)
    {
        vector<long> x;
        for (int i = 0; i < n; i++)
        {
            char p, q;
            long s, t;
            cin >> p >> s >> q >> t;

            if (p == q)
                res += abs(s - t);
            else
                res += 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];
        for (long s : x)
            res += abs(u - s);
    }
    else if (k == 2)
    {
        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)
                res += s - t;
            else
            {
                u.push_back({s, t});

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

                res += 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, (int)oset.size()));
                }
                int j = oset.find_by_order(i)->first;
                pref[i + 1] = purs.sum(j + 1) - vals[j] * (2 * (i + 1) - (int)oset.order_of_key(pair(j, 0)) - (int)oset.order_of_key(pair(j + 1, 0))) - purs.sum(0, j);
            }
        }
        {
            PURS<long> purs(z);
            OrderedSet<pair<int, int>> oset;
            for (int i = m - 1; i >= 0; i--)
            {
                for (long x : u[i])
                {
                    int l = idx(x);
                    purs.add(l, x);
                    oset.insert(pair(l, (int)oset.size()));
                }
                int j = oset.find_by_order(m - i - 1)->first;
                suff[i] = purs.sum(j + 1) - vals[j] * (2 * (m - i) - (int)oset.order_of_key(pair(j, 0)) - (int)oset.order_of_key(pair(j + 1, 0))) - purs.sum(0, j);
            }
        }

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

        res += dist;
    }

    cout << res << '\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: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37