#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
void PlayGround() {
int k, n;
cin>>k>>n;
int s[n], t[n];
vector<int>pts;
long long ans = 0;
for(int i=0; i<n; ++i) {
char p, q;
cin>>p>>s[i]>>q>>t[i];
if(s[i]>t[i]) swap(s[i], t[i]);
if(p==q) {
ans += t[i] - s[i];
--i;
--n;
} else {
pts.push_back(s[i]);
pts.push_back(t[i]);
}
}
if(n==0) {
cout<<ans<<'\n';
return;
}
sort(pts.begin(), pts.end());
pts.resize(unique(pts.begin(), pts.end())-pts.begin());
int m = pts.size();
long long best = INF;
for(int i=0; i<m; ++i) {
int x = pts[i];
long long cur = 0;
map<int,int>come, gone;
vector<pair<int,int>>bag;
for(int j=0; j<n; ++j) {
if(s[j]>x) {
bag.emplace_back(s[j], t[j]);
come[s[j]]++;
gone[t[j]]--;
}
cur += abs(s[j]-x) + abs(t[j]-x);
}
set<int>new_pts;
for(int j=i; j<m; ++j) {
new_pts.insert(pts[j]);
}
for(int j=0; j<bag.size(); ++j) {
int new_point = bag[j].second + bag[j].first - x;
gone[new_point]++;
new_pts.insert(new_point);
}
int c1 = 0, c2 = bag.size();
while(!new_pts.empty()) {
int y = *new_pts.begin();
new_pts.erase(y);
best = min(best, cur);
if(new_pts.empty()) break;
int next_point = *new_pts.begin();
if(gone.count(y)) c1 -= gone[y];
if(come.count(y)) c2 -= come[y];
long long len = next_point - y;
cur += -c2 * 2 * len + c1 * 2 * len;
}
}
ans += best + n;
cout<<ans<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
Compilation message
bridge.cpp: In function 'void PlayGround()':
bridge.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int j=0; j<bag.size(); ++j) {
| ~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
340 KB |
Output is correct |
5 |
Correct |
3 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
320 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
8 ms |
324 KB |
Output is correct |
9 |
Correct |
5 ms |
340 KB |
Output is correct |
10 |
Correct |
12 ms |
320 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
12 ms |
352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
360 KB |
Output is correct |
5 |
Correct |
3 ms |
320 KB |
Output is correct |
6 |
Correct |
1 ms |
320 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
10 ms |
356 KB |
Output is correct |
9 |
Correct |
4 ms |
212 KB |
Output is correct |
10 |
Correct |
9 ms |
360 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
12 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
10 ms |
376 KB |
Output is correct |
15 |
Correct |
1154 ms |
624 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
6 ms |
340 KB |
Output is correct |
18 |
Correct |
132 ms |
432 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1275 ms |
628 KB |
Output is correct |
21 |
Correct |
550 ms |
544 KB |
Output is correct |
22 |
Correct |
1270 ms |
628 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1216 ms |
616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
360 KB |
Output is correct |
5 |
Correct |
2 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
14 ms |
352 KB |
Output is correct |
9 |
Correct |
6 ms |
316 KB |
Output is correct |
10 |
Correct |
10 ms |
356 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
11 ms |
368 KB |
Output is correct |
13 |
Correct |
1 ms |
324 KB |
Output is correct |
14 |
Correct |
13 ms |
340 KB |
Output is correct |
15 |
Correct |
952 ms |
620 KB |
Output is correct |
16 |
Correct |
1 ms |
248 KB |
Output is correct |
17 |
Correct |
8 ms |
320 KB |
Output is correct |
18 |
Correct |
157 ms |
424 KB |
Output is correct |
19 |
Correct |
1 ms |
352 KB |
Output is correct |
20 |
Correct |
1190 ms |
732 KB |
Output is correct |
21 |
Correct |
530 ms |
524 KB |
Output is correct |
22 |
Correct |
1249 ms |
624 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1214 ms |
608 KB |
Output is correct |
25 |
Correct |
25 ms |
3076 KB |
Output is correct |
26 |
Correct |
578 ms |
4576 KB |
Output is correct |
27 |
Execution timed out |
2061 ms |
30136 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |