제출 #890760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
890760		dwuy	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	696 ms	10092 KiB

bridge

/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;

int n, K, sum;
int b[MX];
int c[MX];
pii a[MX];
pii Q[MX];
vector<int> id;

void nhap(){
    cin >> K >> n;
    int t = 0;
    for(int i=1; i<=n; i++){
        int l, r; char t1, t2;
        cin >> t1 >> l >> t2 >> r;
        if(l > r) swap(l, r);
        sum += r-l;
        if(t1 != t2) a[++t] = {l, r};
    }
    n = t;
    sum += n;
    if(n==0) cout << sum, exit(0);
}

int lower_bound_B(int x){
    int res = 0;
    for(int lo=1, hi=n; lo<=hi;){
        int mid = (lo+hi)>>1;
        if(b[mid] - b[mid-1] <= x) res = mid, lo = mid + 1;
        else hi = mid  - 1;
    }
    return res;
}

void subK1(){
    int l=0, r=1;
    int res = OO;
    for(int x: id){
        while(l<n && b[l+1] - b[l] <= x) l++;
        while(r<=n && c[r] - c[r+1] <= x) r++;
        res = min(res, (x*l - b[l] + c[r] - x*(n-r+1))*2);
    }
    cout << res + sum;
}

int calc(int mid){
    int res = OO, cur = 0;
    int qID = 0;
    cur = id[mid]*(lower_bound_B(id[mid])) - b[lower_bound_B(id[mid])];
    for(int i=1; i<=n; i++) if(a[i].fi>id[mid]){
        Q[++qID] = {a[i].se + a[i].fi - id[mid], a[i].se};
        cur += a[i].fi - id[mid];
    }
    sort(Q+1, Q+1+qID);
    int j = n+1;
    int Extra = 0;
    priority_queue<int, vector<int>, greater<int>> extraQ;
    for(int i=(int)id.size()-1; i>mid; i--){
        while(qID && Q[qID].fi - id[i] >= 0){
            cur = cur - (Q[qID].fi - Q[qID].se) + id[i] - Q[qID].se + Extra;
            extraQ.push(id[i] - Q[qID].se + Extra);
            qID--;
        }
        while(extraQ.size() && extraQ.top() <= Extra){
            cur -= extraQ.top();
            extraQ.pop();
        }
        while(c[j-1] - c[j] >= id[i]) j--;
        res = min(res, cur - Extra*(int)extraQ.size() + c[j] - id[i]*(n-j+1) );
        Extra += id[i] - id[i-1];
    }
    return res*2;
}

void subK2(){
    int res = OO;
    for(int lo=0, hi=(int)id.size()/2; lo<=hi;){
        int mid = (lo+hi)>>1;
        if(lo+1>=hi){
            res = min({res, calc(lo), calc(hi)});
            break;
        }
        int cost1 = calc(mid-1);
        int cost2 = calc(mid+1);
        if(cost1 < cost2) res = min(res, cost1), hi = mid;
        if(cost1 > cost2) res = min(res, cost2), lo = mid;
        if(cost1 == cost2) res = min(res, calc(mid)), lo=hi+1;
    }

    for(int lo=(int)id.size()/4 + 1, hi=(int)id.size()/2; lo<=hi;){
        int mid = (lo+hi)>>1;
        if(lo+1>=hi){
            res = min({res, calc(lo), calc(hi)});
            break;
        }
        int cost1 = calc(mid-1);
        int cost2 = calc(mid+1);
        if(cost1 < cost2) res = min(res, cost1), hi = mid;
        if(cost1 > cost2) res = min(res, cost2), lo = mid;
        if(cost1 == cost2) res = min(res, calc(mid)), lo=hi+1;
    }

    // for(int lo=(int)id.size()/2, hi=(int)id.size()/4*3; lo<=hi;){
    //     int mid = (lo+hi)>>1;
    //     if(lo+1>=hi){
    //         res = min({res, calc(lo), calc(hi)});
    //         break;
    //     }
    //     int cost1 = calc(mid-1);
    //     int cost2 = calc(mid+1);
    //     if(cost1 < cost2) res = min(res, cost1), hi = mid;
    //     if(cost1 > cost2) res = min(res, cost2), lo = mid;
    //     if(cost1 == cost2) res = min(res, calc(mid)), lo=hi+1;
    // }
    cout << res + sum << endl;
}

void solve(){
    id.resize(n+n);
    for(int i=1; i<=n; i++){
        id[i-1] = a[i].fi;
        id[i+n-1] = a[i].se;
        b[i] = a[i].se;
        c[i] = a[i].fi;
    }
    sort(id.begin(), id.end());
    id.erase(unique(id.begin(), id.end()), id.end());

    sort(a+1, a+1+n);
    sort(b+1, b+1+n);
    sort(c+1, c+1+n);
    for(int i=1; i<=n; i++) b[i] += b[i-1];
    for(int i=n; i>=1; i--) c[i] += c[i+1];


    if(K==1){
        subK1();
        return;
    }
    if(K==2){
        subK2();
        return;
    }
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

/**

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


**/

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