#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#define N 100002
#define INF 2000000000
#define min2(x,y) (x<y?x:y)
using namespace std;
int n, K;
long long dp1[N], dp2[N];
pair<int, int> in[N];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q1;
priority_queue<pair<int, int> > Q2;
bool cmp(pair<int, int> x, pair<int, int> y) {
// return x.first + x.second < y.first + y.second;
return x < y;
}
int main() {
//freopen("input.txt", "r", stdin);
int k, x, y;
char in_a, in_b;
long long R = 0;
scanf("%d %d ", &K, &k);
while (k--) {
scanf("%c %d %c %d ", &in_a, &x, &in_b, &y);
if (x > y) x += y, y = x - y, x -= y;
R += (long long)(y - x);
if (in_a != in_b) R++, in[++n] = { x,y };
} sort(in + 1, in + n + 1, cmp);
k = 0, x = 0, y = 0;
for (int i = 1; i <= n; i++) {
dp1[i] = dp1[i - 1];
if (k < in[i].first) {
y++, dp1[i] += (long long)(in[i].first - k);
Q1.push({ in[i].first,1 }), Q1.push({ in[i].second,2 });
}
else if (in[i].second < k)
x++, dp1[i] += (long long)(k - in[i].second);
else Q1.push({ in[i].second,2 });
while (Q1.empty() == false && x <= y) {
dp1[i] += (long long)(Q1.top().first - k)*(long long)(x - y);
if (Q1.top().second == 1) y--;
else x++;
k = Q1.top().first, Q1.pop();
}
}
k = in[n].second, x = 0, y = 0;
for (int i = n; i >= 1; i--) {
dp2[i] = dp2[i + 1];
if (in[i].second < k) {
x++, dp2[i] += (long long)(k - in[i].second);
Q2.push({ in[i].second,1 }), Q2.push({ in[i].first,2 });
}
else if (in[i].first > k)
y++, dp2[i] += (long long)(in[i].first - k);
else Q2.push({ in[i].first,2 });
while (Q2.empty() == false && x >= y) {
dp2[i] += (long long)(k - Q2.top().first)*(long long)(y - x);
if (Q2.top().second == 1) x--;
else y++;
k = Q2.top().first, Q2.pop();
}
}
if (K == 1) printf("%lld", R + dp1[n] * 2);
else {
long long MIN = INF;
for (int i = 0; i <= n; i++) MIN = min2(MIN, dp1[i] + dp2[i + 1]);
printf("%lld", R + MIN * 2);
}
}
Compilation message
bridge.cpp: In function 'int main()':
bridge.cpp:27:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d ", &K, &k);
^
bridge.cpp:29:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c %d %c %d ", &in_a, &x, &in_b, &y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 4 |
Correct |
1 ms |
3520 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
3520 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3520 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 4 |
Correct |
1 ms |
3520 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
3520 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
3520 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
3520 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3520 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
3520 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
