#include <bits/stdc++.h>
#define ll long long
#define db double
#define imx INT_MAX
#define imn INT_MIN
#define lmx LLONG_MAX
#define lmn LLONG_MIN
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_llset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
struct pair_t {
ll l, r;
};
int main() {
// ifstream cin("fortmoo.in");
// ofstream cout("fortmoo.out");
ll k, n, i, s, t;
cin >> k >> n;
char p, q;
ll ans = 0;
vector<pair_t> pairs;
for (i = 0; i < n; i++) {
cin >> p >> s >> q >> t;
if (s > t) swap(s, t);
ans += t - s;
if (p != q) {
pairs.push_back({s, t});
ans++;
}
}
sort(pairs.begin(), pairs.end(), [](const pair_t& a, const pair_t& b){return a.l + a.r == b.l + b.r ? a.l < b.l : a.l + a.r < b.l + b.r;});
n = pairs.size();
vector<ll> lbest(n), rbest(n);
priority_queue<ll> lo;
priority_queue<ll, vector<ll>, greater<ll>> hi;
auto cmp1 = [](const pair_t& a, const pair_t& b){return a.l > b.l;};
auto cmp2 = [](const pair_t& a, const pair_t& b){return a.r > b.r;};
priority_queue<pair_t, vector<pair_t>, decltype(cmp2)> mid(cmp2);
priority_queue<pair_t, vector<pair_t>, decltype(cmp1)> right(cmp1);
ll leftcnt = 0, cur = 0, prevmed = 0, median;
for (i = 0; i < n; i++) {
hi.push(pairs[i].l);
hi.push(pairs[i].r);
while (hi.size() > lo.size()) {
lo.push(hi.top());
hi.pop();
}
median = lo.top();
cur += (median - prevmed) * leftcnt * 2;
cur -= (median - prevmed) * right.size() * 2;
if (median >= pairs[i].r) {
leftcnt++;
cur += abs(median - pairs[i].r) * 2;
} else if (median < pairs[i].l) {
right.push(pairs[i]);
cur += abs(pairs[i].l - median) * 2;
} else mid.push(pairs[i]);
while (not right.empty() and median > right.top().l) {
cur += (median - right.top().l) * 2;
mid.push(right.top());
right.pop();
}
while (not mid.empty() and median > mid.top().r) {
cur += (median - mid.top().r) * 2;
leftcnt++;
mid.pop();
}
lbest[i] = cur;
prevmed = median;
}
reverse(pairs.begin(), pairs.end());
for (i = 0; i < n; i++) {
ll tmp = -pairs[i].l;
pairs[i].l = -pairs[i].r + (ll) 1e9;
pairs[i].r = tmp + (ll) 1e9;
}
while (not lo.empty()) lo.pop();
while (not hi.empty()) hi.pop();
while (not mid.empty()) mid.pop();
while (not right.empty()) right.pop();
leftcnt = 0;
cur = 0;
prevmed = 0;
for (i = 0; i < n; i++) {
hi.push(pairs[i].l);
hi.push(pairs[i].r);
while (not hi.empty() and hi.size() > lo.size()) {
lo.push(hi.top());
hi.pop();
}
median = lo.top();
cur += (median - prevmed) * leftcnt * 2;
cur -= (median - prevmed) * (ll) right.size() * 2;
if (median >= pairs[i].r) {
leftcnt++;
cur += abs(median - pairs[i].r) * 2;
} else if (median < pairs[i].l) {
right.push(pairs[i]);
cur += abs(pairs[i].l - median) * 2;
} else mid.push(pairs[i]);
while (not right.empty() and median > right.top().l) {
cur += (median - right.top().l) * 2;
mid.push(right.top());
right.pop();
}
while (not mid.empty() and median > mid.top().r) {
cur += (median - mid.top().r) * 2;
leftcnt++;
mid.pop();
}
rbest[n - i - 1] = cur;
prevmed = median;
}
ll add = rbest[0];
if (k == 1) {
cout << ans + add;
return 0;
}
for (i = 0; i < n - 1; i++) add = min(add, lbest[i] + rbest[i + 1]);
cout << ans + add;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
