이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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<pii> 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(mkp(v[i].f, 2 * i));
st.insert(mkp(v[i].s, 2 * i + 1));
if(v[i].f > med && v[i].s > med){
med = (*st.find_by_order(i)).f;
a += med;
b += v[i].f + v[i].s - med;
}
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(mkp(v[i].f, 2 * i));
st.insert(mkp(v[i].s, 2 * i + 1));
if(v[i].f < med && v[i].s < med){
med = (*st.find_by_order(n - i)).f;
a += v[i].f + v[i].s - med;
b += med;
}
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... |