#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll k,n;
vector<pair<int,pair<ll,ll>>> v,ordx,ordy;
/*
ll f(ll puente){
//cout << "puente: " << puente << endl;
ll res = 0;
for(auto par : v){
ll x = par.first;
ll y = par.second;
if(x <= puente && puente <= y){
res += (y-x+1);
}else{
res += (abs(puente - x) + abs(puente - y) + 1);
}
//cout << res << endl;
}
return res;
}
*/
ll f2(ll puente,ll sol){
ll lo = 0, hi = v.size()-1;
ll res1,res2;
while(lo <= hi){
int mid = (lo+hi)/2;
if(ordx[mid].second.first > puente){
res1 = mid;
hi = mid-1;
}else{
lo = mid+1;
}
}
lo = 0; hi = v.size()-1;
while(lo <= hi){
int mid = (lo+hi)/2;
if(ordy[mid].second.second < puente){
res2 = mid;
lo = mid+1;
}else{
hi = mid-1;
}
}
vector<bool> usado(n,false);
for(int i=0; i<res1+1; i++){
ll x = ordx[i].second.first;
ll y = ordx[i].second.second;
ll ind = ordx[i].first;
sol -= (y-x+1);
sol += (abs(puente - x) + abs(puente - y) + 1);
usado[ind] = true;
}
for(int i=res2; i<(int)ordy.size(); i++){
ll ind = ordy[i].first;
if(usado[ind])continue;
ll x = ordy[i].second.first;
ll y = ordy[i].second.second;
sol -= (y-x+1);
sol += (abs(puente - x) + abs(puente - y) + 1);
}
//cout << puente << " " << sol << endl;
return sol;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> k >> n;
ll sol = 0;
ll mayor = 0;
for(int i=0; i<n; i++){
ll x,y;
char a,b;
cin >> a >> x >> b >> y;
mayor = max(mayor,x);
mayor = max(mayor,y);
if(a == b){
sol += abs(x-y);
}else{
if(x > y){
swap(x,y);
}
v.push_back({i,{x,y}});
sol += (y-x+1);
}
}
ordx = ordy = v;
sort(begin(ordx),end(ordx),[] (const pair<int,pair<ll,ll>> & a, const pair<int,pair<ll,ll>>& b){
return a.second.first <= b.second.first;
});
sort(begin(ordy),end(ordy),[] (const pair<int,pair<ll,ll>> & a, const pair<int,pair<ll,ll>>& b){
return a.second.second <= b.second.second;
});
vector<bool> usado(n,false);
//Ternary search
ll lb = 0, ub = mayor;
while(lb+2 < ub){
//cout << lb << " " << ub << endl;
ll m1 = lb + (lb+ub)/3;
ll m2 = ub - (lb+ub)/3;
//cout << m1 << " " << f(m1) << " " << m2 << " " << f(m2) << endl;
if(m1 > m2)break;
if(f2(m1,sol) <= f2(m2,sol)){
ub = m2-1;
}else{
lb = m1+1;
}
}
ll res = 1e18;
for(ll i=lb; i<=ub; i++){
res = min(res,f2(i,sol));
}
cout << res << endl;
}
Compilation message
bridge.cpp: In function 'll f2(ll, ll)':
bridge.cpp:28:8: warning: 'res1' may be used uninitialized in this function [-Wmaybe-uninitialized]
28 | ll res1,res2;
| ^~~~
bridge.cpp:28:13: warning: 'res2' may be used uninitialized in this function [-Wmaybe-uninitialized]
28 | ll res1,res2;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
