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<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 300004
#define INF 1e9+7
using namespace std;
ll n,k;
pi ar[N];
ll b,d;
char a,c;
ll ans,cnt;
ll mini = INF,maxi = 0;
ll checkbridge(ll x)
{
ll bridge = x;
ll res = ans;
rep(j,0,cnt)
{
if(ar[j].first <= bridge && bridge <= ar[j].second)
continue;
else if(bridge < ar[j].first)
res += 2*(ar[j].first - bridge);
else
res += 2*(bridge-ar[j].second);
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> k >> n;
rep(i,0,n)
{
cin >> a >> b >> c >> d;
if(d < b)
swap(b,d);
ans += d-b;
if(a != c)
{
ar[cnt].first = b;
ar[cnt].second = d;
ans++;
cnt++;
mini = min(mini,b);
maxi = max(maxi,d);
}
}
sort(ar,ar+cnt);
ll fin = INF;
/* rep(i,0,cnt)
{
fin = min(fin,checkbridge(ar[i].first));
fin = min(fin,checkbridge(ar[i].second));
}*/
rep(i,mini,maxi+1)
{
fin = min(fin,checkbridge(i));
}
cout << fin;
return 0;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/
# | 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... |