This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
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
{
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,ans=1e18;
for(long long i=1;i<=c;i++)
{
cntr-=l[i];
cntl+=r[i];
curr+=(cntl-cntr)*2*(opp[i]-opp[i-1]);
ans=min(ans,curr+other);
//cout<<l[i]<<" "<<r[i]<<" "<<curr+other<<" "<<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
*/
Compilation message (stderr)
bridge.cpp: In function 'void read()':
bridge.cpp:36: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]
36 | for(long long i=0;i<v.size();i++)
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |