This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int N = 100005;
struct segtree
{
int t[4 * N] = { 0 };
void add(int v, int l, int r, int pos, int val)
{
if (l == r)
{
t[v] += val;
return;
}
int m = (l + r) / 2;
if (pos <= m)
add(v * 2, l, m, pos, val);
else
add(v * 2 + 1, m + 1, r, pos, val);
t[v] = t[v * 2] + t[v * 2 + 1];
}
int get(int v, int l, int r, int i, int j)
{
if (i > j)
return 0;
if (l == i && r == j)
return t[v];
int m = (l + r) / 2;
return
get(v * 2, l, m, i, min(m, j)) +
get(v * 2 + 1, m + 1, r, max(m + 1, i), j);
}
int get(int v, int l, int r, int pos)
{
if (t[v] == 0)
return mod;
if (l == r)
return l;
int m = (l + r) / 2;
if (pos <= m && t[v * 2])
return get(v * 2, l, m, pos);
return get(v * 2 + 1, m + 1, r, pos);
}
};
LL n;
LL ans, a[3][N];
segtree p[2];
int main()
{
fastIO;
cin >> n;
for (int i = 1; i <= n + n; i++)
{
LL x, y;
cin >> x >> y;
if (x < 1)
{
ans += 1ll - x;
x = 1;
}
else if (x > n)
{
ans += x - n;
x = n;
}
if (y < 1)
{
ans += 1ll - y;
y = 1;
}
else if (y > 2)
{
ans += y - 2ll;
y = 2;
}
a[y][x]++;
p[y].add(1, 1, n, x, 1);
}
for (int i = 1; i <= n; i++)
{
int c[3] = { 0, p[1].get(1, 1, n, i, i), p[2].get(1, 1, n, i, i) };
if(c[2]==0 && c[1]>=2)
{
p[2].add(1, 1, n, i, 1);
c[2]++;
p[1].add(1, 1, n, i, -1);
c[1]--;
ans++;
}
if (c[1] == 0 && c[2] >= 2)
{
p[1].add(1, 1, n, i, 1);
c[1]++;
p[2].add(1, 1, n, i, -1);
c[2]--;
ans++;
}
LL nxt[3] = { 0 };
for (int j = 1; j <= 2; j++)
{
if (c[j])
continue;
nxt[1] = p[1].get(1, 1, n, i + 1);
nxt[2] = p[2].get(1, 1, n, i + 1);
if (nxt[j] < nxt[3 - j] + 1 || (nxt[j] == nxt[3 - j] + 1 && p[j].get(1, 1, n, i + 1, n) >= p[3 - j].get(1, 1, n, i + 1, n)))
{
p[j].add(1, 1, n, nxt[j], -1);
ans += nxt[j] - (LL)i;
c[j]++;
}
else
{
p[3 - j].add(1, 1, n, nxt[3 - j], -1);
c[j]++;
ans += nxt[3 - j] - (LL)i;
ans++;
}
}
if (i == n)
continue;
c[1]--;
c[2]--;
ans += c[1];
ans += c[2];
p[1].add(1, 1, n, i + 1, c[1]);
p[2].add(1, 1, n, i + 1, c[2]);
}
cout << ans << endl;
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... |