#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
int n, k;
#define fi first
#define se second
priority_queue<int> L, R;
ll f[N], cur = 0, sumL = 0, sumR = 0;
void insert(int x) {
if (L.empty() || x <= L.top()) {
L.emplace(+x);
sumL += x;
} else {
R.emplace(-x);
sumR += x;
}
if (L.size() - 1 > R.size()) {
int x = L.top();
R.emplace(-x);
sumR += x;
L.pop();
sumL -= x;
}
if (L.size() < R.size()) {
int x = -R.top();
L.emplace(x);
sumL += x;
R.pop();
sumR -= x;
}
// Ltop*Lsize - sum_l + sum_r - Ltop*Rsize
// = L.top() * (L.size() - R.size()) + sumR - sumL
cur = L.top() * (L.size() - R.size()) + sumR - sumL;
}
int main() {
cin.tie(0)->sync_with_stdio(0); cout.tie(0);
cin >> k >> n;
char p, q;
vector<pair<int, int>> vec;
ll same = 0;
for (int i = 1, s, t; i <= n; ++i) {
cin >> p >> s >> q >> t;
if (p == q) {
same += abs(s - t);
} else {
same += 1;
vec.emplace_back(s, t);
}
}
sort(vec.begin(), vec.end(), [](pair<int, int>& u, pair<int, int>& v) {
return u.fi + u.se < v.fi + v.se;
});
for (int i = 0; i < vec.size(); ++i) {
insert(vec[i].fi);
insert(vec[i].se);
f[i] = cur;
}
if (k == 1) {
cout << cur + same;
return 0;
}
ll res = cur;
L = R = priority_queue<int>();
cur = sumR = sumL = 0;
for (int i = vec.size() - 1; i; --i) {
insert(vec[i].fi);
insert(vec[i].se);
res = min(res, f[i - 1] + cur);
}
cout << res + same;
return 0;
}
Compilation message
bridge.cpp: In function 'int main()':
bridge.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 0; i < vec.size(); ++i) {
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
22 ms |
4284 KB |
Output is correct |
13 |
Correct |
47 ms |
5572 KB |
Output is correct |
14 |
Correct |
37 ms |
4276 KB |
Output is correct |
15 |
Correct |
27 ms |
3572 KB |
Output is correct |
16 |
Correct |
34 ms |
5064 KB |
Output is correct |
17 |
Correct |
36 ms |
5412 KB |
Output is correct |
18 |
Correct |
45 ms |
5024 KB |
Output is correct |
19 |
Correct |
42 ms |
5384 KB |
Output is correct |
20 |
Correct |
30 ms |
5332 KB |
Output is correct |
21 |
Correct |
39 ms |
5096 KB |
Output is correct |
# |
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 |
468 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 |
- |