This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define PrintDec(d, c) cout << fixed << setprecision(c) << d
#define MultiTest(q) long long q; cin >> q; while (q--)
#define rall(v) v.rbegin(), v.rend()
#define all(v) v.begin(), v.end()
#define endl "\n"
#define NAME "BRIDGES"
#define ull unsigned long long int
#define ll long long int
#define pii pair <int, int>
#define pll pair <ll, ll>
bool minimize (ll &a, ll b) {
if (a > b) {
return a = b, true;
}
return false;
}
bool maximize (ll &a, ll b) {
if (a < b) {
return a = b, true;
}
return false;
}
struct Pedestrian {
int s, t;
bool operator< (const Pedestrian &X) const {
return s + t < X.s + X.t;
}
};
const int N = 2E5 + 25;
priority_queue <int, vector<int>> L;
priority_queue <int, vector<int>, greater<int>> R;
int n, m, s, t, k;
vector <int> V;
vector <Pedestrian> A;
char c1, c2;
ll D, T, v1, v2, F[N], G[N];
signed main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
if (fopen(NAME".INP", "r")) {
freopen(NAME".INP", "r", stdin);
freopen(NAME".OUT", "w", stdout);
}
cin >> k >> n;
V.push_back(0);
A.push_back({0, 0});
for (int i = 1; i <= n; i++) {
cin >> c1 >> s >> c2 >> t;
if (c1 == c2) D += llabs(s - t);
else {
if (s > t) swap(s, t);
A.push_back({s, t});
++m;
V.push_back(s);
V.push_back(t);
}
}
D += m;
if (k == 1) {
v1 = v2 = 0;
sort(V.begin(), V.end());
for (int i = 1; i <= 2 * m; i++) {
v1 += abs(V[m] - V[i]);
v2 += abs(V[m + 1] - V[i]);
}
cout << D + min(v1, v2);
}
else {
sort(A.begin(), A.end());
v1 = v2 = 0;
for (int i = 1; i <= m; i++) {
L.push(A[i].s); R.push(A[i].t);
v1 += A[i].s; v2 += A[i].t;
if (L.top() > R.top()) {
int u = L.top(), v = R.top();
v1 += v - u;
v2 += u - v;
L.pop(); R.pop();
L.push(v); R.push(u);
}
F[i] = v2 - v1;
}
while (L.size()) L.pop();
while (R.size()) R.pop();
v1 = v2 = 0;
for (int i = m; i >= 1; i--) {
L.push(A[i].s); R.push(A[i].t);
v1 += A[i].s; v2 += A[i].t;
if (L.top() > R.top()) {
int u = L.top(), v = R.top();
v1 += v - u;
v2 += u - v;
L.pop(); R.pop();
L.push(v); R.push(u);
}
G[i] = v2 - v1;
}
T = F[1] + G[2];
for (int i = 2; i < m; i++)
minimize(T, F[i] + G[i + 1]);
cout << D + T;
}
return 0;
}
Compilation message (stderr)
bridge.cpp: In function 'int main()':
bridge.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | freopen(NAME".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | freopen(NAME".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |