제출 #490578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490578		DeadlyCritic	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	203 ms	28592 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;
}

int sumer(pair<int, int> a){
    return a.fr+a.sc;
}

int sumer(int a, int b){
    return a+b;
}

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();

    if(sz == 1){
        cout << 0 << '\n';
        return 0;
    }

    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);
    }
    
    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;
    }

    int po = 0, qo = 0;
    ll now = 0;
    int l0 = en[po].size(), l1 = 0, r0 = 0, r1 = 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;

    priority_queue<pair<int, int>> pq;

    while(po+1 < sz){
        ll delt = demp[po+1]-demp[po];
        now -= (r1-r0)*2*delt;
        ans = min(ans, now);
        po++;
        
        r1 -= st[po].size();
        for(auto i : en[po]){
            r0++;
            pq.push({-sumer(pr[i]), i});
        }

        while(pq.size() && -pq.top().fr <= po+qo){
            r0--;
            l1++;
            pq.pop();
        }
        

        while(qo+1 < po){
            ll delt = demp[qo+1]-demp[qo];
            ll nxt = now;
            nxt -= (l1-l0)*2*delt;

            if(nxt > now)break;

            qo++;

            while(pq.size() && -pq.top().fr <= po+qo){
                r0--;
                l1++;
                pq.pop();
            }
            l1 -= en[qo].size();
            l0 += en[qo].size();
        }
    }

    cout << fix+ans << '\n';

}

/*

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

===

24

===

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

===

22

===

*/

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