Submission #1134570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134570		g4yuhg	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	44 ms	6588 KiB

bridge

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 500005
using namespace std;
ll k, n;
ll ans_goc = 0;
pii a[N];
vector<ll> nenSo;
void sub1() {
    ll ans = inf;
    sort(a + 1, a + 1 + n);
    ll sum = 0;
    ll cur_p = -1;
    ll cnt_r = n, cnt_l = 0;
    for (int i = 1; i <= n; i ++) {
        ll l = a[i].fi, r = a[i].se;
        //cout << i << " " << l << " " << r << " " << sum << endl;
        sum += (r - l) + min(abs(r - cur_p), abs(l - cur_p)) * 2 + 1;
    }
    //cout << "sum bd: " << sum << endl;
    ans = min(ans, sum);
    ll id = 1;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (int i = 1; i < nenSo.size(); i ++) {
        ll nxt_p = nenSo[i];
        while (pq.size() && pq.top().fi < nxt_p) {
            cnt_l ++ ;
            pq.pop();
        }
        sum -= cnt_r * (nxt_p - cur_p) * 2;
        sum += cnt_l * (nxt_p - cur_p) * 2;
        while (id <= n && a[id].fi <= nxt_p) {
            cnt_r -- ;
            pq.push({a[id].se, id});
            id ++ ;
        }
        //cout << i << " " << nxt_p << " " << sum << endl; 
        ans = min(ans, sum);
        cur_p = nxt_p;
    }
    cout << ans + ans_goc;
}
signed main(void) {
    faster;
    ll curid = 0;
    cin >> k >> n;
    for (int i = 1; i <= n; i ++) {
        char bs1, bs2; ll p1, p2;
        cin >> bs1 >> p1 >> bs2 >> p2;
        if (bs1 == bs2) {
            ans_goc += abs(p1 - p2);
            continue;
        }
        curid ++ ;
        if (p1 > p2) swap(p1, p2);
        a[curid] = {p1, p2};
        nenSo.push_back(p1);
        nenSo.push_back(p2);
    }
    n = curid;
    nenSo.push_back(-inf);
    sort(nenSo.begin(), nenSo.end());
    nenSo.resize(unique(nenSo.begin(), nenSo.end()) - nenSo.begin());
    if (k == 1) {
        sub1();
    }
    return 0;
}

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