Submission #897377

#	Time	Username	Problem	Language	Result	Execution time	Memory
897377		Wobert	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	55 ms	11220 KiB

bridge

#include "bits/stdc++.h"
#ifdef LOCAL
#include "dbg.h"
#else
#define dbg(...) 0
#endif

#define fox(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define rin(i, a, b) for (int i = (a); i <= (b); ++i)
#define rrep(i, a, b) for (int i = (a); i >= (b); --i)
#define fore(x, v) for (auto &&x : v)
#define forp(a, b, v) for (auto &&[a, b] : v)
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define EL "\n"

using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<>>;

template<class T>
int sz(T& container) {
    return (int) container.size();
}
template<class T> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); }
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); }

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//ll urand(int a, int b) { return rng() % (b-a+1) + a; }

//const vector<pii> deltas = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int INF = 0x3f3f3f3f;

template<int MOD, int RT> struct mint {
    static const int mod = MOD;
    static constexpr mint rt() { return RT; } // primitive root for FFT
    int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
    mint():v(0) {}
    mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
        if (v < 0) v += MOD; }
    bool operator==(const mint& o) const {
        return v == o.v; }
    friend bool operator!=(const mint& a, const mint& b) {
        return !(a == b); }
    friend bool operator<(const mint& a, const mint& b) {
        return a.v < b.v; }

    mint& operator+=(const mint& o) {
        if ((v += o.v) >= MOD) v -= MOD;
        return *this; }
    mint& operator-=(const mint& o) {
        if ((v -= o.v) < 0) v += MOD;
        return *this; }
    mint& operator*=(const mint& o) {
        v = int((ll)v*o.v%MOD); return *this; }
    mint& operator/=(const mint& o) { return (*this) *= inv(o); }
    friend mint pow(mint a, ll p) {
        mint ans = 1; assert(p >= 0);
        for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans; }
    friend mint inv(const mint& a) { assert(a.v != 0);
        return pow(a,MOD-2); }

    mint operator-() const { return mint(-v); }
    mint& operator++() { return *this += 1; }
    mint& operator--() { return *this -= 1; }
    friend mint operator+(mint a, const mint& b) { return a += b; }
    friend mint operator-(mint a, const mint& b) { return a -= b; }
    friend mint operator*(mint a, const mint& b) { return a *= b; }
    friend mint operator/(mint a, const mint& b) { return a /= b; }

    friend istream& operator>> (istream& is, mint& a) {
        is >> a.v;
        return is;
    }
    friend ostream& operator<< (ostream& os, const mint& a) {
        os << a.v;
        return os;
    }
};

using mi = mint<int(1e9+7), 5>;

struct bridge {
    pq<ll> left; // sz(left) >= sz(right)
    pqg<ll> right;
    ll cost{};
    // median = left.top()

    void adjust(bool l) {
        ll old, dif;
        if (l) {
            if (sz(left) - sz(right) <= 1) return;
            old = left.top(); left.pop();
            dif = left.top() - old;
        } else {
            if (sz(left) >= sz(right)) return;
            old = right.top(); right.pop();
            dif = old - left.top();
            cost -= dif;
        }
        cost += dif * sz(left);
        cost -= dif * sz(right);
        if (l) right.push(old);
        else left.push(old);
    }

    void insert(ll p) {
        if (left.empty()) {
            left.push(p); return;
        }
        cost += abs(p - left.top());
        if (p > left.top()) {
            right.push(p);
            adjust(false);
        } else {
            left.push(p);
            adjust(true);
        }
    }

    void insert(pll p) {
        insert(p.F); insert(p.S);
    }
};


void solve() {
    int k, n; cin >> k >> n;
    ll ans = 0;
    vpll v;
    fox(i, n) {
        char a, b; int x, y; cin >> a >> x >> b >> y;
        if (a == b) ans += abs(x-y);
        else {
            v.eb(minmax(x, y)); ++ans;
        }
    }
    sort(all(v), [](pll a, pll b) {return a.F+a.S < b.F+b.S;});

    n = sz(v);
    vll lcost(n+1), rcost(n+1);
    bridge l, r;
    rin(i, 1, n) {
        l.insert(v[i-1]);
        r.insert(v[n-i]);
        lcost[i] = l.cost;
        rcost[i] = r.cost;
    }
    ll best;
    if (k == 1) {
        best = lcost[n];
    } else {
        best = 1e18;
        rin(i, 0, n)
            ckmin(best, lcost[i] + rcost[n-i]);
    }
    cout << best + ans << EL;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    int t;
//    cin >> t;
//    while (t--)
        solve();
    return 0;
}

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