#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz(x) (int)x.size()
#define ff first
#define ss second
const int N = 300005;
const int M = 1e9 + 7;
int T, n, k, s1[N], s2[N];
char c1[N], c2[N];
vector <int> p, f;
int f1(int x){
int p1 = (lower_bound(p.begin(),p.end(), x) - p.begin() - 1), f1 = (upper_bound(f.begin(), f.end(), x) - f.begin());
int y = 0;
if(p1 >= 0) y += p[p1];
if(f1 < sz(f)) y += f[f1];
return y;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> k >> n;
int ans = 0;
for(int i = 1; i <= n; i++){
cin >> c1[i] >> s1[i] >> c2[i] >> s2[i];
}
if(k == 1){
int ans1 = 0;
vector <pair <int,int>> v;
for(int i = 1; i <= n; i++){
ans1 += abs(s1[i]-s2[i]);
if(c1 != c2) {
v.push_back({min(s1[i],s2[i]),max(s1[i],s2[i])});
}
}
sort(v.begin(), v.end());
ans1 += sz(v);
vector <int> df, ds;
p.assign(sz(v),0);
f.assign(sz(v),0);
for(int i = 0; i < sz(v); i++){
df.push_back(v[i].ff);
ds.push_back(v[i].ss);
}
sort(ds.begin(), ds.end());
int x = 0;
for(int i = 0; i < sz(v)-1; i++){
x += (ds[i+1]-ds[i]) * (i+1);
p[i] = x;
}
x = 0;
int cnt = 0;
for(int i = sz(v)-1; i > 0; i--){
cnt++;
x += (df[i]-df[i-1]) * cnt;
f[i] = x;
}
int mn = 1e9;
for(int i = 0; i < sz(v); i++){
mn = min(f1(df[i]),mn);
mn = min(f1(ds[i]),mn);
}
// cout << mn + ans1 << '\n';
cout << mn + ans1 << "\n";
return 0;
}
cout << -1;
return 0;
}
Compilation message
bridge.cpp: In function 'int main()':
bridge.cpp:30:6: warning: unused variable 'ans' [-Wunused-variable]
30 | int ans = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
