#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int,int>> notSame; // min et le max
int N;
struct traj {
int l,r;
int mid;
};
vector<traj> a;
int calculate(int x1, int x2){
int s=0;
for (int i = 0; i < a.size(); i++)
{
int s1=abs(x1-a[i].l)+1+abs(x1-a[i].r);
int s2=abs(x2-a[i].l)+1+abs(x2-a[i].r);
s+=min(s1,s2);
}
return s;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n,k; cin >> k >> n;
N=n;
int sum=0;
vector<int> b;
for (int i = 0; i < n; i++){
char p,q; int s,t; cin >> p >> s >> q >> t;
if(p!=q) {
double mid=(((double)s+(double)t)/(double)2);
traj element=traj{s, t, mid};
a.push_back(element);
b.push_back(s);
b.push_back(t);
}else {
sum+=abs(s-t);
}
}
sort(b.begin(),b.end());
N=a.size();
int mn=1e12;
if(N==0) mn=0;
for (int i = 0; i < 2*N; i++)
{
int l=0,r=(2*N)-1;
while((r-l)>1){
int midLEFT=l+(r-l)/3;
int midRIGHT=r-(r-l)/3;
if(calculate(b[i], b[midLEFT])>calculate(b[i], b[midRIGHT])){
l=midLEFT+1;
}else{
r=midRIGHT-1;
}
}
for (int j = l; j <= r; j++)
{
mn=min(mn,calculate(b[i],b[j]));
}
}
cout << mn+sum << "\n";
return 0;
}
Compilation message
bridge.cpp: In function 'long long int calculate(long long int, long long int)':
bridge.cpp:16:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<traj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:36:37: warning: narrowing conversion of 'mid' from 'double' to 'long long int' [-Wnarrowing]
36 | traj element=traj{s, t, mid};
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
168 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
464 KB |
Output is correct |
3 |
Incorrect |
165 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
3 ms |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
472 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
344 KB |
Output is correct |
8 |
Correct |
2 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
344 KB |
Output is correct |
11 |
Correct |
2 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
164 ms |
516 KB |
Output is correct |
14 |
Correct |
159 ms |
348 KB |
Output is correct |
15 |
Correct |
157 ms |
344 KB |
Output is correct |
16 |
Correct |
14 ms |
492 KB |
Output is correct |
17 |
Correct |
46 ms |
348 KB |
Output is correct |
18 |
Correct |
23 ms |
492 KB |
Output is correct |
19 |
Incorrect |
168 ms |
508 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
158 ms |
492 KB |
Output is correct |
14 |
Correct |
169 ms |
504 KB |
Output is correct |
15 |
Correct |
166 ms |
512 KB |
Output is correct |
16 |
Correct |
14 ms |
348 KB |
Output is correct |
17 |
Correct |
44 ms |
348 KB |
Output is correct |
18 |
Correct |
21 ms |
344 KB |
Output is correct |
19 |
Incorrect |
163 ms |
512 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |