Submission #761751

#	Time	Username	Problem	Language	Result	Execution time	Memory
761751		bgnbvnbv	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	161 ms	17296 KiB

bridge

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e5+100;
const ll inf=1e18;
const ll mod=1e9+7;
ll tonglmax=0,tonglmin=0,tongrmax=0,tongrmin=0;
multiset<ll> msmax,msmin;
multiset<ll> ::iterator it;
void cb()
{
    while((ll)msmax.size()-(ll)msmin.size()>1)
    {
        it=msmax.end();
        it--;
        ll x=*it;
        msmax.erase(it);
        msmin.insert(x);
        tongrmax-=x;
        tongrmin+=x;
    }
    while((ll)msmax.size()-(ll)msmin.size()<0)
    {
        it=msmin.begin();
        ll x=*it;
        msmin.erase(it);
        msmax.insert(x);
        tongrmin-=x;
        tongrmax+=x;
    }
}
void xoa(ll x)
{
    it=msmax.end();
    it--;
    if(x<=*it) msmax.erase(msmax.find(x)),tongrmax-=x;
    else
    {
        tongrmin-=x;
        msmin.erase(msmin.find(x));
    }
    cb();
}
ll get()
{
    it=msmax.end();
    it--;
    ll x=*it;
    //cout <<msmax.size()<<' '<<msmin.size()<<'\n';;
    return x*msmax.size()-tongrmax+tongrmin-x*msmin.size();
}
ll k;
ll n;
ll l[maxN],r[maxN];
char p[maxN],q[maxN];
vector<pli>vec;
bool cmp(pli x,pli y)
{
    return x.fi+x.se<y.fi+y.se;
}
ll ans=0;
void solve()
{
    cin >>k>> n;
    for(int i=1;i<=n;i++)
    {
        cin >> p[i] >> l[i] >> q[i] >> r[i];
        if(l[i]>r[i]) swap(l[i],r[i]);
        if(p[i]==q[i])
        {
            ans+=r[i]-l[i];
        }
        else
        {
            vec.pb({l[i],r[i]});
        }
    }
    sort(vec.begin(),vec.end(),cmp);
    priority_queue<ll>pqmax;
    priority_queue<ll,vector<ll>,greater<ll>> pqmin;
    for(int i=0;i<vec.size();i++)
    {
        msmax.insert(vec[i].fi);
        msmax.insert(vec[i].se);
        tongrmax+=vec[i].fi+vec[i].se;
    }
    if(vec.size()==0)
    {
        cout << ans;
        return;
    }
    cb();
    ll add=inf;
    if(k==1)
    {
        add=get();
        cout << add+ans+vec.size();
        return;
    }
    for(int i=0;i<vec.size()-1;i++)
    {
        xoa(vec[i].fi);
        xoa(vec[i].se);
        cb();
        if(i==0)
        {
            pqmax.push(vec[i].fi);
            pqmin.push(vec[i].se);
            tonglmax=vec[i].fi;
            tonglmin=vec[i].se;
        }
        else
        {
            if(vec[i].fi<=pqmax.top()) pqmax.push(vec[i].fi),tonglmax+=vec[i].fi;
            else pqmin.push(vec[i].fi),tonglmin+=vec[i].fi;
            if(vec[i].se<=pqmax.top()) pqmax.push(vec[i].se),tonglmax+=vec[i].se;
            else pqmin.push(vec[i].se),tonglmin+=vec[i].se;
            // pqmax>=pqmin
            while((ll)pqmax.size()-(ll)pqmin.size()>1)
            {
                ll x=pqmax.top();
                pqmax.pop();
                tonglmax-=x;
                pqmin.push(x);
                tonglmin+=x;
            }
            while((ll)pqmax.size()-(ll)pqmin.size()<0)
            {
                ll x=pqmin.top();
                pqmin.pop();
                tonglmax+=x;
                pqmax.push(x);
                tonglmin-=x;
            }
        }
        ll sum=0;
        ll med=pqmax.top();
        sum=med*pqmax.size()-tonglmax+tonglmin-med*pqmin.size();
        sum+=get();
        if(k==2) add=min(add,sum);
    }
    cout << ans+add+vec.size();
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

bridge.cpp: In function 'void solve()':
bridge.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0;i<vec.size();i++)
      |                 ~^~~~~~~~~~~
bridge.cpp:106:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i=0;i<vec.size()-1;i++)
      |                 ~^~~~~~~~~~~~~

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