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>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;
using namespace std;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)
using ll = long long;
using ld = long double;
template<typename T>
using vv = vector<vector<T>>;
using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;
using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;
template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;
const ll M = 1000000007;
const ll infll = M * M;
maxq<int> l;
minq<int> r;
ll ls, rs;
void insert(int x) {
// if (!l.empty() && x > l.top()) {
// r.push(x);
// rs += x;
// } else {
// l.push(x);
// ls += x;
// }
// int msz = (l.size() + r.size() + 1) / 2;
// if (l.size() > msz) {
// int z = l.top();
// l.pop();
// r.push(z);
// ls -= z;
// rs += z;
// } else if (l.size() < msz) {
// int z = r.top();
// r.pop();
// l.push(z);
// rs -= z;
// ls += z;
// }
int median = (l.size() ? l.top() : 1000000001);
if (x <= median) {
l.push(x);
ls += x;
} else {
r.push(x);
rs += x;
}
if (r.size() + 1 < l.size()) {
int nxt = l.top();
l.pop();
r.push(nxt);
ls -= nxt;
rs += nxt;
} else if (l.size() < r.size()) {
int nxt = r.top();
r.pop();
l.push(nxt);
rs -= nxt;
ls += nxt;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int k, n;
cin >> k >> n;
ll res{};
vii pe;
int same_side{};
F0R(i, n) {
char p, q;
int s, t;
cin >> p >> s >> q >> t;
if (p == q) same_side += abs(t - s);
else pe.pb({s, t});
}
n = pe.size();
same_side += n; // distance from people crossing the bridge
sort(all(pe), [&](const ii& a, const ii& b) -> bool {
return a[0] + a[1] < b[0] + b[1];
});
vll pres(n+1); // prefix res
ls = rs = 0;
F0R(i, n) {
insert(pe[i][0]);
insert(pe[i][1]);
pres[i+1] = rs - ls;
}
res += pres[n];
if (k == 2) {
r = {};
l = {};
ls = rs = 0;
R0F(i, n) {
insert(pe[i][0]);
insert(pe[i][1]);
smin(res, pres[i] + rs - ls);
}
}
cout << res + same_side << '\n';
}
# | 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... |