Submission #1272020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272020		bbldrizzy	Palembang Bridges (APIO15_bridge)	C++20	41 / 100	2095 ms	7724 KiB

bridge

#include <bits/stdc++.h>
#include <ios>
#include <iostream>
#include <set>
#include <random>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define f first
#define s second
const int MOD = 1e9+7;
const ll inf = 4*1e18;
const int mx = 5*1e5+5;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int main() {
    // freopen("input.in", "r", stdin);
    // freopen("lifeguards.in", "r", stdin);
    // freopen("lifeguards.out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, k; cin >> k >> n;
    vector<pair<ll, P>> v;
    ll ans = 0;
    vector<ll> st1;
    ll tot1 = 0;
    ll low1 = 0;
    vector<ll> st2;
    ll tot2 = 0;
    ll low2 = 0;
    for (int i = 0; i < n; i++) {
        char t1, t2; ll a, b; cin >> t1 >> a >> t2 >> b;
        if (t1 == t2) {
            ans += abs(a-b);
        } else {
            v.push_back({a+b, {a, b}});
        }
    }
    sort(v.begin(), v.end());
    // for (auto it: st2) {
    //     cout << it << "\n";
    // }
    ll nm = v.size();
    vector<ll> med1(nm);
    for (int i = 1; i < nm; i++) {
        ll a = v[i-1].s.f; ll b = v[i-1].s.s;
        if (st1.empty()) {
            tot1 = a+b;
            low1 = min(a, b);
            st1.push_back(min(a, b));
            st1.push_back(max(a, b));
        } else {
            tot1 += (a+b);
            ll mid = st1[(st1.size()-1)/2];
            if (a <= mid && b <= mid) {
                low1 -= mid;
                low1 += (a+b);
            } else if (a > mid && b > mid) {
                low1 += min({a, b, st1[(st1.size())/2]});
            } else {
                low1 += min(a, b);
            }
            auto p1 = lower_bound(st1.begin(), st1.end(), a);
            st1.insert(p1, a);
            auto p2 = lower_bound(st1.begin(), st1.end(), b);
            st1.insert(p2, b);
        }
        // cout << "tot1: " << tot1 << "\n";
        // cout << "low1: " << low1 << "\n";
        med1[i] = tot1-2*low1;
    }
    // for (auto it: med1) {
    //     cout << it << "\n";
    // }
    vector<ll> med2(nm);
    for (int i = nm-1; i > 0; i--) {
        ll a = v[i].s.f; ll b = v[i].s.s;
        if (st2.empty()) {
            tot2 = a+b;
            low2 = min(a, b);
            st2.push_back(min(a, b));
            st2.push_back(max(a, b));
        } else {
            tot2 += (a+b);
            ll mid = st2[(st2.size()-1)/2];
            if (a <= mid && b <= mid) {
                low2 -= mid;
                low2 += (a+b);
            } else if (a > mid && b > mid) {
                low2 += min({a, b, st2[(st2.size())/2]});
            } else {
                low2 += min(a, b);
            }
            auto p1 = lower_bound(st2.begin(), st2.end(), a);
            st2.insert(p1, a);
            auto p2 = lower_bound(st2.begin(), st2.end(), b);
            st2.insert(p2, b);
        }
        // cout << "tot1: " << tot1 << "\n";
        // cout << "low1: " << low1 << "\n";
        med2[i] = tot2-2*low2;
    }
    // for (auto it: med2) {
    //     cout << it << "\n";
    // }
    ll mn = (nm > 0 ? inf : 0);
    for (int i = 1; i <= nm-1; i++) {
        mn = min(mn, med1[i]+med2[i]);
    }
    cout << mn+ans+nm;
}

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