제출 #328624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
328624		Mahdi_Shokoufi	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	420 ms	21584 KiB

bridge

//In The Name of Allah
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int , int > pii;
typedef pair < ll , ll > pll;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())

const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1e9 + 10;

ll P[2][N], ps[2][N], a[2][N], pre[N], suf[N];
vector < ll > vec;
vector < pll > seg;

bool cmp(pll x, pll y){
    return (x.X + x.Y) < (y.X + y.Y);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, k, m = 1, ans = 0, EXT = 0;
    cin >> k >> n;
    for (ll i = 1; i <= n; i ++){
        char c1, c2;
        ll x1, x2;
        cin >> c1 >> x1 >> c2 >> x2;
        if (c1 == c2)
            ans += abs(x1 - x2), EXT += abs(x1 - x2);
        else{
            P[c1 - 'A'][m] = x1;
            P[c2 - 'A'][m] = x2;
            a[c1 - 'A'][m] = x1;
            a[c2 - 'A'][m] = x2;
            seg.pb(mp(x1, x2));
            vec.pb(x1);
            vec.pb(x2);
            m ++;
            ans ++;
        }
    }
    P[0][m] = inf;
    P[1][m] = inf;
    vec.pb(inf);
    m ++;
    P[0][m] = inf + 1;
    P[1][m] = inf + 1;
    vec.pb(inf + 1);
    m ++;
    sort(P[0] + 1, P[0] + m);
    sort(P[1] + 1, P[1] + m);
    for (ll i = 1; i < m; i ++){
        ps[0][i] = ps[0][i - 1] + P[0][i];
        ps[1][i] = ps[1][i - 1] + P[1][i];
    }
    vec.resize(unique(all(vec)) - vec.begin());
    ll res = inf * inf;
    if (k == 1){
        for (ll x : vec){
            ll cost = 0;
            ll p1 = upper_bound(P[0] + 1, P[0] + m, x) - P[0];
            ll p2 = upper_bound(P[1] + 1, P[1] + m, x) - P[1];
            cost += (p1 - 1) * x - ps[0][p1 - 1];
            cost += (p2 - 1) * x - ps[1][p2 - 1];
            cost += ps[0][m - 3] - ps[0][p1 - 1] - x * (m - p1 - 2);
            cost += ps[1][m - 3] - ps[1][p2 - 1] - x * (m - p2 - 2);
            res = min(res, cost);
        }
        cout << ans + res;
        return 0;
    }
    if (seg.empty())
        return cout << ans, 0;
    sort(all(seg), cmp);
    multiset < ll > mnH, mxH; ll mnS = 0, mxS = 0;
    mnH.insert(min(seg[0].X, seg[0].Y)); mnS += min(seg[0].X, seg[0].Y);
    mxH.insert(max(seg[0].X, seg[0].Y)); mxS += max(seg[0].X, seg[0].Y);
    pre[1] = mxS - mnS;
    for (ll i = 2; i <= sz(seg); i ++){
       if (seg[i - 1].X <= *mxH.begin()){
           mnH.insert(seg[i - 1].X);
           mnS += seg[i - 1].X;
       }
       else{
           auto itr = mxH.begin();
           mxS -= *itr;
           mnS += *itr;
           mnH.insert(*itr);
           mxH.erase(itr);
           mxS += seg[i - 1].X;
           mxH.insert(seg[i - 1].X);
       }
       if (seg[i - 1].Y <= *mxH.begin()){
           mnH.insert(seg[i - 1].Y);
           mnS += seg[i - 1].Y;
       }
       else{
           auto itr = mxH.begin();
           mxS -= *itr;
           mnS += *itr;
           mnH.insert(*itr);
           mxH.erase(itr);
           mxS += seg[i - 1].Y;
           mxH.insert(seg[i - 1].Y);
       }
       if (sz(mnH) < sz(mxH)){
           auto itr = mxH.begin();
           mxS -= *itr;
           mnS += *itr;
           mnH.insert(*itr);
           mxH.erase(itr);
       }
       if (sz(mxH) < sz(mnH)){
           auto itr = mnH.rbegin();
           mnS -= *itr;
           mxS += *itr;
           mxH.insert(*itr);
           mnH.erase(mnH.find(*itr));
       }
       pre[i] = mxS - mnS;
    }
    mnH.clear(); mxH.clear(); mnS = mxS = 0;
    mnH.insert(min(seg.back().X, seg.back().Y)); mnS += min(seg.back().X, seg.back().Y);
    mxH.insert(max(seg.back().X, seg.back().Y)); mxS += max(seg.back().X, seg.back().Y);
    suf[sz(seg)] = mxS - mnS;
    for (ll i = sz(seg) - 1; i >= 1; i --){
       if (seg[i - 1].X <= *mxH.begin()){
           mnH.insert(seg[i - 1].X);
           mnS += seg[i - 1].X;
       }
       else{
           auto itr = mxH.begin();
           mxS -= *itr;
           mnS += *itr;
           mnH.insert(*itr);
           mxH.erase(itr);
           mxS += seg[i - 1].X;
           mxH.insert(seg[i - 1].X);
       }
       if (seg[i - 1].Y <= *mxH.begin()){
           mnH.insert(seg[i - 1].Y);
           mnS += seg[i - 1].Y;
       }
       else{
           auto itr = mxH.begin();
           mxS -= *itr;
           mnS += *itr;
           mnH.insert(*itr);
           mxH.erase(itr);
           mxS += seg[i - 1].Y;
           mxH.insert(seg[i - 1].Y);
       }
       if (sz(mnH) < sz(mxH)){
           auto itr = mxH.begin();
           mxS -= *itr;
           mnS += *itr;
           mnH.insert(*itr);
           mxH.erase(itr);
       }
       if (sz(mxH) < sz(mnH)){
           auto itr = mnH.rbegin();
           mnS -= *itr;
           mxS += *itr;
           mxH.insert(*itr);
           mnH.erase(mnH.find(*itr));
       }
       suf[i] = mxS - mnS;
    }
    ll ANS = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000;
    for (int i = 0; i <= sz(seg); i ++)
        ANS = min(ANS, pre[i] + suf[i + 1] + EXT + sz(seg));
    cout << ANS;
    return 0;
}

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