Submission #583103

#	Time	Username	Problem	Language	Result	Execution time	Memory
583103		gg123_pe	Palembang Bridges (APIO15_bridge)	C++14	31 / 100	216 ms	11280 KiB

bridge

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
typedef pair<ll,ll> ii; 

#define f(i,a,b) for(ll i = a; i < b; i++)
#define fa(i,a,b) for(ll i = a; i >= b; i--)

const int N = 30005; 
const ll inf = 1e9, INF = 1e18;


int k, n; 
ll ans, mini; 
set <ll> pos; 
vector <ii> v; 

ll get(ll i, ll j){   
    ll res = 0; 
    for(auto p: v){
        ll a = p.first, b = p.second; 
        res += 1 + min(abs(a-i)+abs(b-i), abs(a-j)+abs(b-j)); 
    }
    return res; 
}
ll ge(ll i){   
    ll res = 0; 
    for(auto p: v){
        ll a = p.first, b = p.second; 
        if(i < a) res += a + b + 1 - 2*i; 
        else if(b < i) res += 2*i + 1 - a - b; 
        else res += b - a + 1; 
    }
    return res; 
}
int main(){
    cin >> k >> n; 

    f(i,1,n+1){
        char x, y; 
        ll a, b; 

        cin >> x >> a >> y >> b; 
        
        if(x == y){
            ans += abs(b-a);
        }
        else{
            v.push_back({min(a,b), max(a, b)}); 
            pos.insert(a), pos.insert(b); 
        }
    }

    ll mini = INF; 

      ll l = 0, r = inf; 
 
    while(l < r){
        ll m = (l+r)>>1; 
        if(ge(m) < ge(m+1)) r = m; 
        else l = m+1; 
    }
    mini = ge(l); 
   
    if(k == 2){
    vector <ll> ra; 
    for(ll x: pos) ra.push_back(x); 

    int le = ra.size(); 
    f(i,0,le-1){
        ll x = ra[i]; 
        ll l = i+1, r = le-1; 

        while(l < r){
            ll m = (l+r)>>1; 
            if(get(x, ra[m]) < get(x, ra[m+1])) r = m; 
            else l = m+1; 
        }
        mini = min(mini, get(x, ra[l])); 
    }

    }
    cout << ans + mini  << "\n"; 
    return 0;
}

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