Submission #740168

#	Time	Username	Problem	Language	Result	Execution time	Memory
740168		Mauve	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	39 ms	5320 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ss second
#define ff first
#define INF 2000000000000000
#define pb push_back
ll n,m,l,r,i,j,ii,jj,k,x,y,T,s,e,a[100005],b[100005],dist1,dist2,ans,sz1,sz2;
char ch1,ch2;
vector< pair<ll,ll> > v;
vector<ll> sub;
multiset<ll> l1,l2,r1,r2;
multiset<ll>::iterator it;
void nem(ll num){
    ll med=*(--l1.end()),new_med;
    if(num>med) r1.insert(num);
    else l1.insert(num);
    if(l1.size()>(sz1+1)/2){
        it=(--l1.end());
        l1.erase(it);
        r1.insert(*it);
        new_med=*(--l1.end());
        dist1+=((sz1-1)/2+1)*(med-new_med)-(sz1/2-1)*(med-new_med);
    }
    if(r1.size()>sz1/2){
        it=(r1.begin());
        r1.erase(it);
        l1.insert(*it);
        new_med=*it;
        dist1+=(sz1/2)*(new_med-med)-((sz1-1)/2)*(new_med-med);
    }
    dist1+=abs(num-new_med);
}
void has(ll num){
    ll med=*(--l2.end()),new_med;
    if(num>med){
       it=r2.find(num); 
       r2.erase(it); 
    }
    else{
        it=l2.find(num);
        l2.erase(it);
    }
    dist2-=(abs(num-med));
    if(l2.size()>(sz2+1)/2){
        it=(--l2.end());
        l2.erase(it);
        r2.insert(*it);
        new_med=*(--l2.end());
        dist2+=((sz2+1)/2)*(med-new_med)-((sz2+2)/2-1)*(med-new_med);
    }
    if(r2.size()>sz2/2){
        it=(r2.begin());
        r2.erase(it);
        l2.insert(*it);
        new_med=*it;
        dist2+=((sz2+2)/2-1)*(new_med-med)-((sz2+1)/2)*(new_med-med);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>T>>n;
    for(i=1;i<=n;i++){
        cin>>ch1>>l>>ch2>>r;
        if(ch1==ch2) k+=abs(l-r);
        else{
            k++;
            v.pb({l+r,i});
            sub.pb(l);
            sub.pb(r);
        }
        a[i]=l;
        b[i]=r;
    }
    if(T==1){
        sort(sub.begin(),sub.end());
        for(i=0;i<sub.size();i++) k+=abs(sub[i]-sub[sub.size()/2]);
        cout<<k;
        return 0;
    }
    sort(v.begin(),v.end());
    n=v.size();
    if(n==0){
        cout<<k;
        return 0;
    }
    if(n==1){
        cout<<k+abs(a[v[0].ss]-b[v[0].ss]);
        return 0;
    }
    l1.insert(min(a[v[0].ss],b[v[0].ss]));
    r1.insert(max(a[v[0].ss],b[v[0].ss]));
    dist1=abs(a[v[0].ss]-b[v[0].ss]);
      
    for(i=1;i<n;i++){
        r2.insert(a[v[i].ss]);
        r2.insert(b[v[i].ss]);
    }
    for(i=1;i<n;i++){
        it=r2.begin();
        l2.insert(*it);
        r2.erase(it);
    }
    it=l2.end();
    it--;
    x=*it;
    for(i=1;i<n;i++) dist2+=abs(a[v[i].ss]-x)+abs(b[v[i].ss]-x);
    ans=dist2+dist1;
    sz1=2;
    sz2=2*(n-1);
    for(i=1;i<n-1;i++){
        sz1++;
        nem(a[v[i].ss]);
        sz1++;
        nem(b[v[i].ss]);
        sz2--;
        has(a[v[i].ss]);
        sz2--;
        has(b[v[i].ss]);
        ans=min(ans,dist1+dist2);
    }
    cout<<ans+k;
}

Compilation message (stderr)

bridge.cpp: In function 'void nem(long long int)':
bridge.cpp:18:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   18 |     if(l1.size()>(sz1+1)/2){
      |        ~~~~~~~~~^~~~~~~~~~
bridge.cpp:25:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   25 |     if(r1.size()>sz1/2){
      |        ~~~~~~~~~^~~~~~
bridge.cpp: In function 'void has(long long int)':
bridge.cpp:45:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   45 |     if(l2.size()>(sz2+1)/2){
      |        ~~~~~~~~~^~~~~~~~~~
bridge.cpp:52:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   52 |     if(r2.size()>sz2/2){
      |        ~~~~~~~~~^~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:79:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(i=0;i<sub.size();i++) k+=abs(sub[i]-sub[sub.size()/2]);
      |                 ~^~~~~~~~~~~
bridge.cpp: In function 'void nem(long long int)':
bridge.cpp:32:15: warning: 'new_med' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |     dist1+=abs(num-new_med);
      |            ~~~^~~~~~~~~~~~~

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