//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
using namespace std;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
typedef long long ll;
typedef long double ld;
const ll SZ = 2e5 + 100;
#define int ll
ll n;
vector<pair<ll, ll>> vec;
ll svd[SZ][2];
pair<int, int> seg[SZ * 4];
int seg2[SZ * 4];
void upd2(int v, int l, int r, int pos) {
if (l == r - 1) {
seg2[v] = 0;
} else {
int mid = (l + r) / 2;
if (pos < mid) {
upd2(v * 2 + 1, l, mid, pos);
} else {
upd2(v * 2 + 2, mid, r, pos);
}
seg2[v] = seg2[v * 2 + 1] + seg2[v * 2 + 2];
}
}
int ask2(int v, int l, int r, int askl, int askr) {
if (l >= askr || r <= askl) return 0;
if (askl <= l && r <= askr) return seg2[v];
int mid = (l + r) / 2;
int q = ask2(v * 2 + 1, l, mid, askl, askr), q2 = ask2(v * 2 + 2, mid, r, askl, askr);
return q + q2;
}
void upd(int v, int l, int r, int pos, int val, int val2) {
if (l == r - 1) {
seg[v].first += val;
seg[v].second += val2;
} else {
int mid = (l + r) / 2;
if (pos < mid) {
upd(v * 2 + 1, l, mid, pos, val, val2);
} else {
upd(v * 2 + 2, mid, r, pos, val, val2);
}
seg[v] = { seg[v * 2 + 1].first + seg[v * 2 + 2].first, seg[v * 2 + 1].second + seg[v * 2 + 2].second };
}
}
pair<int, int> ask(int v, int l, int r, int askl, int askr) {
if (l >= askr || r <= askl) return { 0, 0 };
if (askl <= l && r <= askr) return seg[v];
int mid = (l + r) / 2;
pair<int, int> q = ask(v * 2 + 1, l, mid, askl, askr), q2 = ask(v * 2 + 2, mid, r, askl, askr);
return { q.first + q2.first, q.second + q2.second };
}
signed main() {
fastInp;
cin >> n;
vec.resize(n * 2);
for (int i = 0; i < n * 2; i++) cin >> vec[i].first >> vec[i].second;
ll ans = 0;
set<ll> hv, er;
for (int i = 0; i < n * 2; i++) {
if (vec[i].first <= 1) {
ans += abs(vec[i].first - 1);
vec[i].first = 1;
}
if (vec[i].first >= n) {
ans += abs(vec[i].first - n);
vec[i].first = n;
}
if (vec[i].second <= 1) {
ans += abs(vec[i].second - 1);
vec[i].second = 1;
}
if (vec[i].second >= 2) {
ans += abs(vec[i].second - 2);
vec[i].second = 2;
}
svd[vec[i].first][vec[i].second - 1]++;
}
for (int i = 1; i <= n; i++) {
hv.insert(i);
upd(0, 0, SZ, i, svd[i][0], svd[i][1]);
}
set<pair<ll, ll>> st;
for (int i = 1; i <= n; i++) {
st.insert({ svd[i][0] + svd[i][1], i });
}
er.insert(0);
er.insert(n + 1);
ll sm = n * 2;
for (int i = 0; i < n; i++) {
//if (seg[0].first + seg[0].second != sm) return 1;
//sm -= 2;
pair<ll, ll> cur;
if (st.size() > 2 && (*(--(--st.end()))).first >= 2) {
cur = (*(--(--st.end())));
st.erase(--(--st.end()));
} else {
cur = (*(--st.end()));
st.erase(--st.end());
}
pair<ll, ll> vals = ask(0, 0, SZ, cur.second, cur.second + 1);
hv.erase(cur.second);
er.insert(cur.second);
upd2(0, 0, SZ, cur.second);
upd(0, 0, SZ, cur.second, -vals.first, -vals.second);
if (vals.first > 0 && vals.second > 0) {
vals.first--;
vals.second--;
} else {
if (vals.first > 0) vals.first -= 2;
if (vals.second > 0) vals.second -= 2;
ans++;
}
if (hv.lower_bound(cur.second) != hv.begin()) {
ll lftPos = *(--hv.lower_bound(cur.second));
ll lftPos2 = 0;
pair<ll, ll> sm = ask(0, 0, SZ, lftPos2 + 1, lftPos + 1);
pair<ll, ll> sm2 = ask(0, 0, SZ, lftPos, lftPos + 1);
st.erase({ sm2.first + sm2.second, lftPos });
ll lng = ask2(0, 0, SZ, 0, lftPos + 1);
lng *= 2;
ll q = min(vals.first, max(sm.second, sm.first) - sm.first);
ll q2 = min(vals.second, max(sm.second, sm.first) - sm.second);
if (sm.first + sm.second < lng) {
upd(0, 0, SZ, lftPos, q, q2);
vals.first -= q;
vals.second -= q2;
sm.first += q;
sm.second += q2;
ans += q * abs(cur.second - lftPos);
ans += q2 * abs(cur.second - lftPos);
lng -= (sm.first + sm.second);
ll mn = min(vals.first, vals.second);
mn = min(mn, lng / 2);
upd(0, 0, SZ, lftPos, mn, mn);
vals.first -= mn;
vals.second -= mn;
sm.first += mn;
sm.second += mn;
ans += mn * abs(cur.second - lftPos);
ans += mn * abs(cur.second - lftPos);
lng = ask2(0, 0, SZ, 0, lftPos + 1);
lng *= 2;
lng -= (sm.first + sm.second);
mn = min(vals.first, lng);
lng -= mn;
upd(0, 0, SZ, lftPos, mn, 0);
vals.first -= mn;
sm.first += mn;
ans += mn * abs(cur.second - lftPos);
mn = min(vals.second, lng);
lng -= mn;
upd(0, 0, SZ, lftPos, 0, mn);
vals.second -= mn;
sm.second += mn;
ans += mn * abs(cur.second - lftPos);
sm2 = ask(0, 0, SZ, lftPos, lftPos + 1);
st.insert({ sm2.first + sm2.second, lftPos });
}
}
if (hv.upper_bound(cur.second) != hv.end()) {
ll lftPos = *(hv.upper_bound(cur.second));
ll lftPos2 = n + 1;
pair<ll, ll> sm = ask(0, 0, SZ, lftPos, lftPos2);
pair<ll, ll> sm2 = ask(0, 0, SZ, lftPos, lftPos + 1);
st.erase({ sm2.first + sm2.second, lftPos });
ll lng = ask2(0, 0, SZ, lftPos, n + 1);
lng *= 2;
ll q = min(vals.first, max(sm.second, sm.first) - sm.first);
ll q2 = min(vals.second, max(sm.second, sm.first) - sm.second);
if (sm.first + sm.second < lng) {
upd(0, 0, SZ, lftPos, q, q2);
vals.first -= q;
vals.second -= q2;
sm.first += q;
sm.second += q2;
ans += q * abs(cur.second - lftPos);
ans += q2 * abs(cur.second - lftPos);
lng -= (sm.first + sm.second);
ll mn = min(vals.first, vals.second);
mn = min(mn, lng / 2);
upd(0, 0, SZ, lftPos, mn, mn);
vals.first -= mn;
vals.second -= mn;
sm.first += mn;
sm.second += mn;
ans += mn * abs(cur.second - lftPos);
ans += mn * abs(cur.second - lftPos);
lng = ask2(0, 0, SZ, lftPos, n + 1);
lng *= 2;
lng -= (sm.first + sm.second);
mn = min(vals.first, lng);
lng -= mn;
upd(0, 0, SZ, lftPos, mn, 0);
vals.first -= mn;
sm.first += mn;
ans += mn * abs(cur.second - lftPos);
mn = min(vals.second, lng);
lng -= mn;
upd(0, 0, SZ, lftPos, 0, mn);
vals.second -= mn;
sm.second += mn;
ans += mn * abs(cur.second - lftPos);
sm2 = ask(0, 0, SZ, lftPos, lftPos + 1);
st.insert({ sm2.first + sm2.second, lftPos });
}
}
}
cout << ans;
return 0;
}
Compilation message
joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:123:8: warning: unused variable 'sm' [-Wunused-variable]
123 | ll sm = n * 2;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
