#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<utility>
#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 100004
#define INF 1e18
using namespace std;
ll n,k;
pi ar[N];
ll b,d;
char a,c;
ll ans,cnt;
vector <ll>possible;
vector < ll > ola;
set < ll > p;
ll abso(ll x)
{
if(x<0)
return -x;
return x;
}
ll checkbridge(ll x,ll y)
{
ll res = ans;
rep(i,0,cnt)
{
if(ar[i].first <= x && x <= ar[i].second)
{
res += ar[i].second-ar[i].first;
}
else if(ar[i].first <= y && y <= ar[i].second)
{
res+=ar[i].second-ar[i].first;
}
else
{
res += 2*min(min(abso(ar[i].first-x),abso(ar[i].second-x)),min(abso(ar[i].first-y),abso(ar[i].second-y)))+(ar[i].second-ar[i].first);
}
}
// cout << x << " " << y << " " << res << endl;
return res;
}
ll findans(ll x)
{
ll low = x;
ll high = possible.size()-1;
ll res = x;
while(low <= high)
{
ll mid = (low+high)/2;
if(checkbridge(possible[x],possible[mid-1]) >= checkbridge(possible[x],possible[mid]))
{
low = mid+1;
res = mid;
}
else
{
high = mid-1;
}
}
ll fin = checkbridge(possible[x],possible[res]);
low = 0;
high = x;
res = 0;
while(low <= high)
{
ll mid = (low+high)/2;
if(checkbridge(possible[x],possible[mid-1]) >= checkbridge(possible[x],possible[mid]))
{
low = mid+1;
res = mid;
}
else
{
high = mid-1;
}
}
return min(fin,checkbridge(possible[x],possible[res]));
}
void solve2()
{
ll fin = checkbridge(possible[0],possible[0]);
rep(i,0,possible.size())
{
if(fin < findans(i))
break;
else
fin = findans(i);
}
cout << fin << endl;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
freopen("bridge_3_3.in","r",stdin);
cin >> k >> n;
rep(i,0,n)
{
cin >> a >> b >> c >> d;
if(d < b)
swap(b,d);
if(a == c)
ans += d-b;
else
{
ar[cnt].first = b;
ar[cnt].second = d;
ola.push_back(b);
ola.push_back(d);
ans++;
cnt++;
}
}
if(cnt == 0)
{
cout << ans;
return 0;
}
rep(i,0,cnt)
{
p.insert(ar[i].first);
p.insert(ar[i].second);
}
for(set < ll >::iterator it = p.begin();it != p.end();it++)
{
possible.push_back(*it);
}
if(k == 2)
{
solve2();
return 0;
}
ll low = 0;
ll high = possible.size()-1;
ll res = 0;
while(low <= high)
{
ll mid = (low+high)/2;
if(checkbridge(possible[mid-1],possible[mid-1]) >= checkbridge(possible[mid],possible[mid]))
{
low = mid+1;
res = mid;
}
else
{
high = mid-1;
}
}
cout << checkbridge(possible[res],possible[res]);
return 0;
}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
2 3
A 1 B 1
A 4 B 7
A 10 B 12
*/
Compilation message
bridge.cpp: In function 'void solve2()':
bridge.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i = a;i < b;i++)
bridge.cpp:110:9:
rep(i,0,possible.size())
~~~~~~~~~~~~~~~~~~~
bridge.cpp:110:5: note: in expansion of macro 'rep'
rep(i,0,possible.size())
^~~
bridge.cpp: In function 'int main()':
bridge.cpp:126:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("bridge_3_3.in","r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
