제출 #563120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
563120		piOOE	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2087 ms	9744 KiB

bridge

//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int

typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;


template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int bit(int x, int b) {
    return (x >> b) & 1;
}

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }


const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18
const int N = 100002;
const int mod = 998244353;
const ld eps = 1e-9;

int A[N], B[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k, n;
    cin >> k >> n;
    ll perm = 0;
    for (int i = 0; i < n; ++i) {
        string s1, s2;
        int x, y;
        cin >> s1 >> x >> s2 >> y;
        perm += abs(x - y);
        if (s1 == s2) {
            --i;
            --n;
            continue;
        }
        perm += 1; //from L to R or otherwise
        if (x > y) swap(x, y);
        A[i] = x, B[i] = y;
    }
    if (n == 0) {
        cout << perm;
        return 0;
    }
    ll ans = infL;
    vector<array<int, 3>> v;
    for (int i = 0; i < n; ++i) {
        v.push_back({A[i], 0, i});
        v.push_back({B[i], 1, i});
    }
    sort(all(v));
    {
        //only one bridge //x, type, i
        int cnt_open = n, cnt_close = 0;
        ll sum_open = accumulate(all(A), 0ll), sum_close = 0;
        for (auto [x, t, i]: v) {
            if (t == 0) {
                --cnt_open;
                sum_open -= x;
            } else if (t == 1) {
                ++cnt_close;
                sum_close += x;
            }
            ckmn(ans, (sum_open - cnt_open * (ll) x) + (cnt_close * (ll) x - sum_close));
        }
    }
    if (k == 2) {
        int m = sz(v);
        vector<int> cntA(m + 1), cntB(m);
        vector<ll> sufA(m + 1), prefB(m);
        for (int i = 0; i < m; ++i) {
            if (i) {
                cntB[i] = cntB[i - 1];
                prefB[i] = prefB[i - 1];
            }
            if (v[i][1]) {
                ++cntB[i];
                prefB[i] += v[i][0];
            }
        }
        for (int i = m - 1; i > -1; --i) {
            cntA[i] = cntA[i + 1];
            sufA[i] = sufA[i + 1];
            if (!v[i][1]) {
                ++cntA[i];
                sufA[i] += v[i][0];
            }
        }
        for (int f = 0; f < m; ++f) {
            ll now = v[f][0] * (ll) cntB[f] - prefB[f];
            normal_queue<pair<ll, int>> pq;
            ll sum = 0;
            int cntt = 0;
            ll sumcnt = 0;
            for (int s = f + 1; s < m; ++s) {
                ll nw = sufA[s] - v[s][0] * (ll) cntA[s];
                if (v[s][1]) {
                    int i = v[s][2];
                    if (A[i] >= v[f][0]) {
                        pq.push(mp(A[i] - v[f][0] + v[s][0], i));
                        sumcnt += v[s][0];
                        cntt += 1;
                    }
                }
                while (!pq.empty() && pq.top().first <= v[s][0]) {
                    cntt -= 1;
                    int i = pq.top().second;
                    sumcnt -= B[i];
                    sum += A[i] - v[f][0];
                    pq.pop();
                }
                ckmn(ans, nw + now + sum + (cntt * (ll)v[s][0] - sumcnt));
            }
        }
    }
    cout << ans * 2 + perm;
    return 0;
}

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