이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define LSB(x) ((x) & -(x))
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const char nl = '\n';
struct OrderedSet{
multiset<int> lo, hi;
ll cost = 0;
int m;
OrderedSet() {}
void Insert(int x){
m = (sz(lo) > 0) ? *lo.rbegin() : x;
cost += abs(x - m);
if (x <= m) lo.insert(x);
else hi.insert(x);
Balance();
}
void Erase(int x){
m = *lo.rbegin();
cost -= abs(x - m);
if (x <= m) lo.erase(lo.find(x));
else hi.erase(hi.find(x));
Balance();
}
void Balance(){
int l = sz(lo)-1, r = sz(hi), new_m = m;
if (sz(hi) > sz(lo)){
int val = *hi.begin();
hi.erase(hi.begin());
lo.insert(val);
new_m = *lo.rbegin();
cost += (new_m - m) * (l + 1 - r);
}
else if (sz(hi) < sz(lo) - 1){
int val = *lo.rbegin();
lo.erase(lo.find(val));
hi.insert(val);
new_m = *lo.rbegin();
cost += (m - new_m) * (r + 1 - l);
}
m = new_m;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int k, n; cin >> k >> n;
ll base = 0;
vector<pair<int, int>> v;
for (int i = 0; i < n; i++){
char z1, z2; int p1, p2;
cin >> z1 >> p1 >> z2 >> p2;
if (z1 == z2) base += abs(p1 - p2);
else {
if (p1 > p2) swap(p1, p2);
v.eb(p1, p2);
base++;
}
}
sort(all(v));
OrderedSet sL, sR;
for (int i = 0; i < sz(v); i++){
sR.Insert(v[i].f);
sR.Insert(v[i].s);
}
ll ans = sR.cost;
if (k == 1) { cout << base + ans << nl; return 0; }
for (int i = 0; i < sz(v); i++){
sR.Erase(v[i].f);
sR.Erase(v[i].s);
sL.Insert(v[i].f);
sL.Insert(v[i].s);
ans = min(ans, sL.cost + sR.cost);
}
cout << base + ans << nl;
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... |