This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define ld long double
#define fi first
#define se second
#define ll long long
#define ss(x) (int) x.size()
#define mp make_pair
#define FOR(i, n) for(int i = 1; n >= i; ++i)
using namespace std;
using namespace __gnu_pbds;
const int nax = 2e5 + 5, inf = 1e9 + 1;
int n;
ll ans = 0;
int t[nax][2];
vector <int> v[2];
void add(int x, int y) {
int px = x, py = y;
if(y >= 2) {
ans += y - 2;
py = 2;
}
else {
ans += 1 - y;
py = 1;
}
if(x < 1) {
ans += 1 - x;
px = 1;
}
else if(x > n) {
ans += x - n;
px = n;
}
py--;
t[px][py]++;
//cout << x << " " << y << " " << px << " " << py << endl;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= 2 * n; ++i) {
int a, b;
cin >> a >> b;
add(a, b);
}
for(int i = 1; i <= n; ++i) {
v[0].pb(i);
v[1].pb(i);
for(int j = 0; j < 2; ++j) {
while(ss(v[j]) && t[i][j]) {
ans += i - v[j].back();
v[j].pop_back();
t[i][j]--;
}
}
for(int j = 0; j < 2; ++j) {
int neg = (j ^ 1);
while(ss(v[neg]) && t[i][j]) {
ans += i - v[neg].back() + 1;
v[neg].pop_back();
t[i][j]--;
}
}
for(int j = 0; j < 2; ++j) {
ans += t[i][j];
t[i + 1][j] += t[i][j];
}
}
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... |