Submission #490576

#	Time	Username	Problem	Language	Result	Execution time	Memory
490576		DeadlyCritic	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	192 ms	30704 KiB

bridge

#include <bits/stdc++.h>
// #pragma GCC optimize ("O2,unroll-loops")
// #pragma GCC optimize("no-stack-protector,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define IOS ios::sync_with_stdio(0), cin.tie(), cout.tie();

#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define uni(v) sort(all(v)), v.erase(unique(all(v)), v.end())

// #define c0 (v << 1)
// #define c1 (c0 | 1)
// #define md ((l+r)>>1)

using namespace std;

typedef long long ll;

const int maxN = 2e5+7;


int k, n, sz;
ll fix;

vector<pair<int, int>> ed;

vector<int> df;

map<int, int> mp;
int demp[maxN];

pair<int, int> pr[maxN];
vector<int> st[maxN], en[maxN];


ll dis(pair<int, int> a, ll p){
    return abs(a.fr-p)+abs(a.sc-p)+1;
}


signed main(){IOS


    cin >> k >> n;
    

    for(int i = 0; i < n; i++){
        char t1, t2;
        int x1, x2;
        cin >> t1 >> x1 >> t2 >> x2;
        if(t1 == t2){
            fix += abs(x2-x1);
        }
        else{
            ed.push_back({min(x1, x2), max(x1, x2)});
            df.push_back(x1);
            df.push_back(x2);
        }
    }

    n = ed.size();

    uni(df);

    sz = df.size();

    for(int i = 0; i < sz; i++)mp[df[i]] = i, demp[i] = df[i];

    for(int i = 0; i < n; i++){
        ed[i].fr = mp[ed[i].fr];
        ed[i].sc = mp[ed[i].sc];
        pr[i] = {ed[i].fr, ed[i].sc};
        st[ed[i].fr].push_back(i);
        en[ed[i].sc].push_back(i);
    }
    
    assert(k == 1);

    if(k == 1){
        int po = 0;
        ll now = 0;
        int l = en[po].size(), r = n-st[po].size();
        for(int i = 0; i < n; i++){
            ll x = dis({demp[ed[i].fr], demp[ed[i].sc]}, demp[po]);
            now += x;
        }
        ll ans = now;

        while(po+1 < sz){
            ll delt = demp[po+1]-demp[po];
            now += (l*2-r*2)*delt;
            ans = min(ans, now);
            po++;
            l += en[po].size();
            r -= st[po].size();
        }

        cout << fix+ans << '\n';
        return 0;
    }

}

/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

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