Submission #1109794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109794		simona1230	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	124 ms	25636 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
 
long long k,n,num;
pair<long long,long long> p[200001];
long long other,curr;
 
long long l[200001],r[200001];
vector<pair<long long,long long> > v;
long long c=0;
map<long long,long long> mp;
long long opp[200001];
int CNT;
 
void read()
{
    cin>>k>>n;
    for(long long i=1;i<=n;i++)
    {
        char c1,c2;
        long long s,f;
        cin>>c1>>s>>c2>>f;
        if(c1!=c2)
        {
            if(s>f)swap(s,f);
            curr+=s+f+1;
            v.push_back({s,1});
            v.push_back({f,2});
        }
        else
        {
            CNT++;
            other+=max(s,f)-min(s,f);
        }
    }
    sort(v.begin(),v.end());
 
    for(long long i=0;i<v.size();i++)
    {
        if(i==0||v[i].first!=v[i-1].first)c++;
        mp[v[i].first]=c;
        opp[c]=v[i].first;
        if(v[i].second==1)l[c]++;
        else r[c]++;
    }
}
 
void solve()
{
    //cout<<curr<<" "<<other<<endl;
    long long cntl=0,cntr=n-CNT,ans=curr+other;
    for(long long i=1;i<=c;i++)
    {
        curr+=(cntl-cntr)*2*(opp[i]-opp[i-1]);
        cntr-=l[i];
        cntl+=r[i];
        ans=min(ans,curr+other);
        //cout<<l[i]<<" "<<r[i]<<" "<<curr<<" "<<cntl<<" "<<cntr<<endl;
    }
    cout<<ans<<endl;
}
 
int main()
{
    read();
    solve();
    return 0;
}
 
/*
 1 5
 B 0 A 4
 B 1 B 3
 A 5 B 7
 B 2 A 6
 B 1 A 7
 
1 3
A 1 B 1
A 5 B 5
A 6 B 6
*/

Compilation message (stderr)

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

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