이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//In The Name of Allah
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair < int , int > pii;
typedef pair < ll , ll > pll;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1e9 + 10;
ll P[2][N], ps[2][N], a[2][N], pre[N], suf[N];
vector < ll > vec;
vector < pll > seg;
bool cmp(pll x, pll y){
return (x.X + x.Y) < (y.X + y.Y);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n, k, m = 1, ans = 0, EXT = 0;
cin >> k >> n;
for (ll i = 1; i <= n; i ++){
char c1, c2;
ll x1, x2;
cin >> c1 >> x1 >> c2 >> x2;
if (c1 == c2)
ans += abs(x1 - x2), EXT += abs(x1 - x2);
else{
P[c1 - 'A'][m] = x1;
P[c2 - 'A'][m] = x2;
a[c1 - 'A'][m] = x1;
a[c2 - 'A'][m] = x2;
seg.pb(mp(x1, x2));
vec.pb(x1);
vec.pb(x2);
m ++;
ans ++;
}
}
P[0][m] = inf;
P[1][m] = inf;
vec.pb(inf);
m ++;
P[0][m] = inf + 1;
P[1][m] = inf + 1;
vec.pb(inf + 1);
m ++;
sort(P[0] + 1, P[0] + m);
sort(P[1] + 1, P[1] + m);
for (ll i = 1; i < m; i ++){
ps[0][i] = ps[0][i - 1] + P[0][i];
ps[1][i] = ps[1][i - 1] + P[1][i];
}
vec.resize(unique(all(vec)) - vec.begin());
ll res = inf * inf;
if (k == 1){
for (ll x : vec){
ll cost = 0;
ll p1 = upper_bound(P[0] + 1, P[0] + m, x) - P[0];
ll p2 = upper_bound(P[1] + 1, P[1] + m, x) - P[1];
cost += (p1 - 1) * x - ps[0][p1 - 1];
cost += (p2 - 1) * x - ps[1][p2 - 1];
cost += ps[0][m - 3] - ps[0][p1 - 1] - x * (m - p1 - 2);
cost += ps[1][m - 3] - ps[1][p2 - 1] - x * (m - p2 - 2);
res = min(res, cost);
}
cout << ans + res;
return 0;
}
if (seg.empty())
return cout << ans, 0;
sort(all(seg), cmp);
multiset < ll > mnH, mxH; ll mnS = 0, mxS = 0;
mnH.insert(min(seg[0].X, seg[0].Y)); mnS += min(seg[0].X, seg[0].Y);
mxH.insert(max(seg[0].X, seg[0].Y)); mxS += max(seg[0].X, seg[0].Y);
pre[1] = mxS - mnS;
for (ll i = 2; i <= sz(seg); i ++){
if (seg[i - 1].X <= *mxH.begin()){
mnH.insert(seg[i - 1].X);
mnS += seg[i - 1].X;
}
else{
auto itr = mxH.begin();
mxS -= *itr;
mnS += *itr;
mnH.insert(*itr);
mxH.erase(itr);
mxS += seg[i - 1].X;
mxH.insert(seg[i - 1].X);
}
if (seg[i - 1].Y <= *mxH.begin()){
mnH.insert(seg[i - 1].Y);
mnS += seg[i - 1].Y;
}
else{
auto itr = mxH.begin();
mxS -= *itr;
mnS += *itr;
mnH.insert(*itr);
mxH.erase(itr);
mxS += seg[i - 1].Y;
mxH.insert(seg[i - 1].Y);
}
if (sz(mnH) < sz(mxH)){
auto itr = mxH.begin();
mxS -= *itr;
mnS += *itr;
mnH.insert(*itr);
mxH.erase(itr);
}
if (sz(mxH) < sz(mnH)){
auto itr = mnH.rbegin();
mnS -= *itr;
mxS += *itr;
mxH.insert(*itr);
mnH.erase(mnH.find(*itr));
}
pre[i] = mxS - mnS;
}
mnH.clear(); mxH.clear(); mnS = mxS = 0;
mnH.insert(min(seg.back().X, seg.back().Y)); mnS += min(seg.back().X, seg.back().Y);
mxH.insert(max(seg.back().X, seg.back().Y)); mxS += max(seg.back().X, seg.back().Y);
suf[sz(seg)] = mxS - mnS;
for (ll i = sz(seg) - 1; i >= 1; i --){
if (seg[i - 1].X <= *mxH.begin()){
mnH.insert(seg[i - 1].X);
mnS += seg[i - 1].X;
}
else{
auto itr = mxH.begin();
mxS -= *itr;
mnS += *itr;
mnH.insert(*itr);
mxH.erase(itr);
mxS += seg[i - 1].X;
mxH.insert(seg[i - 1].X);
}
if (seg[i - 1].Y <= *mxH.begin()){
mnH.insert(seg[i - 1].Y);
mnS += seg[i - 1].Y;
}
else{
auto itr = mxH.begin();
mxS -= *itr;
mnS += *itr;
mnH.insert(*itr);
mxH.erase(itr);
mxS += seg[i - 1].Y;
mxH.insert(seg[i - 1].Y);
}
if (sz(mnH) < sz(mxH)){
auto itr = mxH.begin();
mxS -= *itr;
mnS += *itr;
mnH.insert(*itr);
mxH.erase(itr);
}
if (sz(mxH) < sz(mnH)){
auto itr = mnH.rbegin();
mnS -= *itr;
mxS += *itr;
mxH.insert(*itr);
mnH.erase(mnH.find(*itr));
}
suf[i] = mxS - mnS;
}
ll ANS = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000;
for (int i = 0; i <= sz(seg); i ++)
ANS = min(ANS, pre[i] + suf[i + 1] + EXT + sz(seg));
cout << ANS;
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... |