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>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
#define mkp make_pair
#define pii pair<int, int>
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int MAXN = 1e5 + 5;
int n, k, add;
vector<pii> v;
ordered_set<int> st;
int pref[MAXN], suff[MAXN];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> k >> n;
if(k == 1){
vector<int> temp;
for(int i = 0; i < n; i++){
char a, b;
int x, y;
cin >> a >> x >> b >> y;
if(a == b) add += abs(x - y);
else{
temp.pb(x);
temp.pb(y);
}
}
n = sz(temp) / 2;
sort(all(temp));
int ans = 0;
for(int i = 0; i < 2 * n; i++){
ans += abs(temp[i] - temp[n]);
}
cout << ans + add + n << '\n';
return 0;
}
for(int i = 0; i < n; i++){
char a, b;
int x, y;
cin >> a >> x >> b >> y;
if(a == b) add += abs(x - y);
else v.pb(mkp(x, y));
}
n = sz(v);
if(n == 0){
cout << add << '\n';
return 0;
}
int a = 0, b = 0, med = 0;
sort(all(v), [](pii &p1, pii &p2){
return (p1.f + p1.s) < (p2.f + p2.s);
});
for(int i = 0; i < n; i++){
st.insert(v[i].f);
st.insert(v[i].s);
if(v[i].f > med && v[i].s > med){
med = *st.find_by_order(i);
a += med;
b += v[i].s;
}
else{
a += v[i].f;
b += v[i].s;
}
pref[i] = b - a;
}
while(!st.empty()) st.erase(st.begin());
a = 0, b = 0, med = 1e18;
for(int i = n - 1; i >= 0; i--){
st.insert(v[i].f);
st.insert(v[i].s);
if(v[i].f < med && v[i].s < med){
med = *st.find_by_order(n - i - 1);
a += med;
b += v[i].s;
}
else{
a += v[i].f;
b += v[i].s;
}
suff[i] = b - a;
}
int ans = 1e18;
for(int i = 0; i < n - 1; i++){
ans = min(ans, pref[i] + suff[i + 1]);
}
cout << add + ans + n << '\n';
return 0;
}
# | 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... |