#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
bool cmp (pii p1, pii p2) {
return p1.fi + p1.se < p2.fi + p2.se;
}
int K, N;
vector<pll> A;
void go (vector<ll> &vres) {
set<pll> st = {pll(A[0].fi, 0), pll(A[0].se, 1)};
auto it = st.begin();
ll ans = A[0].se - A[0].fi;
vres.push_back(ans);
for (int i = 1; i < A.size(); i++) {
ll x = A[i].fi, y = A[i].se;
pll px(x, 2 * i), py(y, 2 * i + 1);
st.insert(px);
st.insert(py);
if (py < *it) {
ans += 2 * it->fi - x - y;
it--;
} else if (px > *it) {
it++;
ans += x + y - 2 * it->fi;
} else {
ans += y - x;
}
vres.push_back(ans);
}
}
vector<ll> res[2];
int main() {
scanf("%d %d", &K, &N);
ll ans = 0;
for (int i = 0; i < N; i++) {
int x, y;
char c, d;
scanf(" %c %d %c %d", &c, &x, &d, &y);
if (x > y) {
swap(x, y);
}
if (c == d) {
ans += y - x;
} else {
ans++;
A.push_back({x, y});
}
}
if (!A.empty()) {
sort(all(A), cmp);
go(res[0]);
if (K == 1) {
printf("%lld\n", ans + res[0].back());
return 0;
}
reverse(all(A));
go(res[1]);
ll mnadd = min(res[0].back(), res[1].back());
for (int i = 0; i + 1 < A.size(); i++) {
mnadd = min(mnadd, res[0][i] + res[1][A.size() - 2 - i]);
}
ans += mnadd;
}
printf("%lld\n", ans);
}
Compilation message
bridge.cpp: In function 'void go(std::vector<long long int>&)':
bridge.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < A.size(); i++) {
~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:80:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i + 1 < A.size(); i++) {
~~~~~~^~~~~~~~~~
bridge.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &K, &N);
~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c %d %c %d", &c, &x, &d, &y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
416 KB |
Output is correct |
2 |
Correct |
2 ms |
476 KB |
Output is correct |
3 |
Correct |
3 ms |
524 KB |
Output is correct |
4 |
Correct |
4 ms |
600 KB |
Output is correct |
5 |
Correct |
3 ms |
704 KB |
Output is correct |
6 |
Correct |
4 ms |
744 KB |
Output is correct |
7 |
Correct |
4 ms |
764 KB |
Output is correct |
8 |
Correct |
4 ms |
932 KB |
Output is correct |
9 |
Correct |
6 ms |
932 KB |
Output is correct |
10 |
Correct |
4 ms |
932 KB |
Output is correct |
11 |
Correct |
4 ms |
932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
932 KB |
Output is correct |
2 |
Correct |
3 ms |
932 KB |
Output is correct |
3 |
Correct |
5 ms |
988 KB |
Output is correct |
4 |
Correct |
3 ms |
988 KB |
Output is correct |
5 |
Correct |
4 ms |
1008 KB |
Output is correct |
6 |
Correct |
4 ms |
1180 KB |
Output is correct |
7 |
Correct |
4 ms |
1180 KB |
Output is correct |
8 |
Correct |
3 ms |
1180 KB |
Output is correct |
9 |
Correct |
3 ms |
1180 KB |
Output is correct |
10 |
Correct |
5 ms |
1180 KB |
Output is correct |
11 |
Correct |
4 ms |
1192 KB |
Output is correct |
12 |
Correct |
132 ms |
16740 KB |
Output is correct |
13 |
Correct |
333 ms |
19208 KB |
Output is correct |
14 |
Correct |
243 ms |
19208 KB |
Output is correct |
15 |
Correct |
160 ms |
19208 KB |
Output is correct |
16 |
Correct |
152 ms |
23256 KB |
Output is correct |
17 |
Correct |
203 ms |
25612 KB |
Output is correct |
18 |
Correct |
131 ms |
27616 KB |
Output is correct |
19 |
Correct |
170 ms |
29980 KB |
Output is correct |
20 |
Correct |
160 ms |
31868 KB |
Output is correct |
21 |
Correct |
161 ms |
33916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
33916 KB |
Output is correct |
2 |
Correct |
3 ms |
33916 KB |
Output is correct |
3 |
Correct |
3 ms |
33916 KB |
Output is correct |
4 |
Correct |
3 ms |
33916 KB |
Output is correct |
5 |
Correct |
3 ms |
33916 KB |
Output is correct |
6 |
Correct |
3 ms |
33916 KB |
Output is correct |
7 |
Correct |
3 ms |
33916 KB |
Output is correct |
8 |
Correct |
2 ms |
33916 KB |
Output is correct |
9 |
Correct |
3 ms |
33916 KB |
Output is correct |
10 |
Correct |
3 ms |
33916 KB |
Output is correct |
11 |
Correct |
4 ms |
33916 KB |
Output is correct |
12 |
Correct |
3 ms |
33916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
33916 KB |
Output is correct |
2 |
Correct |
3 ms |
33916 KB |
Output is correct |
3 |
Correct |
3 ms |
33916 KB |
Output is correct |
4 |
Correct |
3 ms |
33916 KB |
Output is correct |
5 |
Correct |
3 ms |
33916 KB |
Output is correct |
6 |
Correct |
3 ms |
33916 KB |
Output is correct |
7 |
Correct |
3 ms |
33916 KB |
Output is correct |
8 |
Correct |
3 ms |
33916 KB |
Output is correct |
9 |
Correct |
2 ms |
33916 KB |
Output is correct |
10 |
Correct |
3 ms |
33916 KB |
Output is correct |
11 |
Correct |
2 ms |
33916 KB |
Output is correct |
12 |
Correct |
3 ms |
33916 KB |
Output is correct |
13 |
Correct |
4 ms |
33916 KB |
Output is correct |
14 |
Correct |
6 ms |
33916 KB |
Output is correct |
15 |
Correct |
5 ms |
33916 KB |
Output is correct |
16 |
Correct |
3 ms |
33916 KB |
Output is correct |
17 |
Correct |
4 ms |
33916 KB |
Output is correct |
18 |
Correct |
4 ms |
33916 KB |
Output is correct |
19 |
Correct |
5 ms |
33916 KB |
Output is correct |
20 |
Correct |
5 ms |
33916 KB |
Output is correct |
21 |
Correct |
4 ms |
33916 KB |
Output is correct |
22 |
Correct |
5 ms |
33916 KB |
Output is correct |
23 |
Correct |
4 ms |
33916 KB |
Output is correct |
24 |
Correct |
2 ms |
33916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
33916 KB |
Output is correct |
2 |
Correct |
2 ms |
33916 KB |
Output is correct |
3 |
Correct |
3 ms |
33916 KB |
Output is correct |
4 |
Correct |
3 ms |
33916 KB |
Output is correct |
5 |
Correct |
2 ms |
33916 KB |
Output is correct |
6 |
Correct |
3 ms |
33916 KB |
Output is correct |
7 |
Correct |
2 ms |
33916 KB |
Output is correct |
8 |
Correct |
2 ms |
33916 KB |
Output is correct |
9 |
Correct |
3 ms |
33916 KB |
Output is correct |
10 |
Correct |
3 ms |
33916 KB |
Output is correct |
11 |
Correct |
2 ms |
33916 KB |
Output is correct |
12 |
Correct |
3 ms |
33916 KB |
Output is correct |
13 |
Correct |
3 ms |
33916 KB |
Output is correct |
14 |
Correct |
4 ms |
33916 KB |
Output is correct |
15 |
Correct |
4 ms |
33916 KB |
Output is correct |
16 |
Correct |
2 ms |
33916 KB |
Output is correct |
17 |
Correct |
3 ms |
33916 KB |
Output is correct |
18 |
Correct |
4 ms |
33916 KB |
Output is correct |
19 |
Correct |
5 ms |
33916 KB |
Output is correct |
20 |
Correct |
6 ms |
33916 KB |
Output is correct |
21 |
Correct |
4 ms |
33916 KB |
Output is correct |
22 |
Correct |
4 ms |
33916 KB |
Output is correct |
23 |
Correct |
5 ms |
33916 KB |
Output is correct |
24 |
Correct |
4 ms |
33916 KB |
Output is correct |
25 |
Correct |
212 ms |
36040 KB |
Output is correct |
26 |
Correct |
346 ms |
36972 KB |
Output is correct |
27 |
Correct |
595 ms |
38668 KB |
Output is correct |
28 |
Correct |
602 ms |
41036 KB |
Output is correct |
29 |
Correct |
424 ms |
43344 KB |
Output is correct |
30 |
Correct |
237 ms |
43344 KB |
Output is correct |
31 |
Correct |
223 ms |
46160 KB |
Output is correct |
32 |
Correct |
242 ms |
48464 KB |
Output is correct |
33 |
Correct |
217 ms |
50636 KB |
Output is correct |
34 |
Correct |
249 ms |
52916 KB |
Output is correct |
35 |
Correct |
246 ms |
54568 KB |
Output is correct |
36 |
Correct |
243 ms |
56700 KB |
Output is correct |
37 |
Correct |
179 ms |
57496 KB |
Output is correct |