#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int MAXN = 2e5+10;
const int INF = 4e18+10;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
int K, n, MX;
int ans, MN = INF;
vector <pii> cc;
int cek(int idx){
int ret = 0, m = 0, c = 0;
int mn = 0;
vector <pii> vec;
for(auto in : cc){
if(in.fi <= idx && idx <= in.se){
ret += in.se-in.fi;
} else if(idx<=in.fi && idx<=in.se){
ret += in.se-idx+in.fi-idx;
} else {
int a = in.fi, b = in.se;
vec.pb({a+b-idx, 0});
vec.pb({a, 1});
vec.pb({b, 1});
c += 2*idx-a-b;
}
}
mn = c;
sort(vec.begin(), vec.end());
for(int i=0; i<vec.size(); i++){
int nw = vec[i].fi;
while(i+1<vec.size() && vec[i+1].fi == vec[i].fi){
// upd i
if(vec[i].se){
m += 2;
c += -2*nw;
} else {
m -= 2;
c += 2*nw;
}
i++;
}
// upd i
if(vec[i].se){
m += 2;
c += -2*nw;
} else {
m -= 2;
c += 2*nw;
}
mn = min(mn, m*nw+c);
}
return ret+mn;
// <a[i]+b[i]-idx,<-2,2*a[i]+2*b[i]-2*idx>>
// <a[i],<2,-2*a[i]>>
// <b[i],<2,-2*b[i]>>
// <a[i]+b[i]-idx,0>
// <a[i],1>
// <b[i],1>
// idx-b[i] <= a[i]-x
// x <= a[i]+b[i]-idx
// 2*idx-a[i]-b[i]
// a[i]+b[i]-idx <= x <= a[i]
// a[i]+b[i]-2x
// a[i] <= x <= b[i]
// b[i]-a[i]
// b[i] <= x
// 2x-a[i]-b[i]
// <a[i],i>
// <b[i],i>
}
void solve(){
cin >> K >> n;
vector <int> v; v.pb(-1);
for(int i=1; i<=n; i++){
char x, y; int a, b;
cin >> x >> a >> y >> b; a++; b++;
if(x==y){
ans += abs(a-b); continue;
}
if(a > b) swap(a, b);
cc.pb({a, b});
v.pb(a); v.pb(b);
}
sort(v.begin(), v.end());
int l=1, r=v.size()-1, mid1=0, mid2=0;
while(r-l+1 >= 210){
mid1 = (l+l+r)/3; mid2 = (l+r+r+2)/3;
int num1 = cek(v[mid1]), num2 = cek(v[mid2]);
// cout << mid1 << " " << mid2 << " " << cek(mid1) << " " << cek(mid2) << endl;
MN = min(MN, min(num1, num2));
if(num1 < num2) r = mid2;
else l = mid1;
}
// cout << l << ' ' << r << " lr\n";
for(int mid=l; mid<=r; mid++){
// cout << mid << " " << cek(mid) << endl;
MN = min(MN, cek(v[mid]));
}
cout << ans + MN + (int)cc.size() << '\n';
ans = 0; MN = INF;
cc.clear(); v.clear();
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// int T = 1;
// while(T--){
// solve();
// }
solve();
}
Compilation message
bridge.cpp: In function 'long long int cek(long long int)':
bridge.cpp:37:19: 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]
37 | for(int i=0; i<vec.size(); i++){
| ~^~~~~~~~~~~
bridge.cpp:39:18: 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]
39 | while(i+1<vec.size() && vec[i+1].fi == vec[i].fi){
| ~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |