Submission #487340

#	Time	Username	Problem	Language	Result	Execution time	Memory
487340		leaked	Palembang Bridges (APIO15_bridge)	C++14	8 / 100	2072 ms	2740 KiB

bridge

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e18;
signed main(){
    fast_iati;

    int k,n;
    cin>>k>>n;
    vec<int>l,r;
    ll ans=0;
    vec<int>kek;
    vec<int>pref;
    for(int i=0;i<n;i++){
        char f,s;
        int x,y;
        cin>>f>>x>>s>>y;
        if(f==s) ans+=abs(x-y);
        else{
            if(x>y) swap(x,y);
            l.pb(x);r.pb(y);
        }
    }
    n=sz(l);
    for(int i=0;i<n;i++){
        kek.pb(l[i]);kek.pb(r[i]);
    }
    sort(all(kek));kek.erase(unique(all(kek)),kek.end());
    pref.assign(sz(kek)+1,0);
    for(int i=0;i<n;i++){
        l[i]=lower_bound(all(kek),l[i])-kek.begin();
        r[i]=lower_bound(all(kek),r[i])-kek.begin();
        pref[l[i]]++,pref[r[i]+1]--;
    }
    for(int i=1;i<=sz(kek);i++){
        pref[i]+=pref[i-1];
    }
    for(int i=0;i<sz(kek);i++){
        int cnt=0;
        for(int k=0;k<n;k++){
            cnt+=(l[k]<=i&&r[k]>=i);
        }
        assert(cnt==pref[i]);
    }
    int j=*max_element(all(pref));
    auto f=[&](int i){
         int x=kek[i];
        ll me=0;
        for(int k=0;k<n;k++){
            me+=abs(x-kek[l[k]]);
            me+=abs(x-kek[r[k]])+1;
        }
        return me;
    };
    if(k==1){
        if(!sz(kek)){
            cout<<ans;
            return 0;
        }
        int tl=0,tr=sz(kek)-1;
        while(tr-tl>=3){
            int t1=tl+(tr-tl)/3;
            int t2=tr-(tr-tl)/3;
            if(f(t1)<f(t2)) tr=t2;
            else tl=t1;
        }
        ll mn=inf;
        for(int i=tl;i<=tr;i++)
            umin(mn,f(i));
//        cout<<ans<<endl;
        cout<<ans+mn;
    }
    else{
    cout<<22;}
    return 0;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:60:9: warning: unused variable 'j' [-Wunused-variable]
   60 |     int j=*max_element(all(pref));
      |         ^

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