#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define len(s) (ll) s.size()
#define LS(x) (1 << x)
const ll I = 2e5 + 9;
const ll Z = 1e9 + 7;
using namespace std;
ll rs = 0;
int n, nex[I], prv[I];
pair<int, int> b[I];
set<int> s;
vector<int> S[I * 4];
struct mix
{
int x, y;
} a[I];
void preST(int x, int l, int r)
{
if (l == r)
{
S[x].assign(1, 0);
return;
}
S[x].assign(r - l + 1, 0);
int mid = (l + r) / 2;
preST(x * 2, l, mid);
preST(x * 2 + 1, mid + 1, r);
}
void build(int x, int l, int r)
{
if (l == r)
{
S[x][0] = b[l].se;
return;
}
int mid = (l + r) / 2;
build(x * 2, l, mid);
build(x * 2 + 1, mid + 1, r);
int id = 0, i1 = 0, i2 = 0;
while (id != r - l + 1)
{
if (i1 == mid - l + 1)
{
S[x][id] = S[x * 2 + 1][i2];
i2++;
id++;
}
else if (i2 == r - mid)
{
S[x][id] = S[x * 2][i1];
i1++;
id++;
}
else if (S[x * 2][i1] < S[x * 2 + 1][i2])
{
S[x][id] = S[x * 2][i1];
i1++;
id++;
}
else
{
S[x][id] = S[x * 2 + 1][i2];
id++;
i2++;
}
}
}
int get(int x, int l, int r, int L, int R, int val)
{
if (r < L || R < l || r < l || R < L)
return 0;
if (L <= l && r <= R)
{
auto id = upper_bound(S[x].begin(), S[x].begin() + (r - l + 1), val) - S[x].begin();
return id;
}
int mid = (l + r) / 2;
return get(x * 2, l, mid, L, R, val) + get(x * 2 + 1, mid + 1, r, L, R, val);
}
void dc(int l, int r)
{
if (l == r)
return;
int mid = (l + r) / 2;
s.clear();
for (int i = mid; i >= l; i--)
{
if (s.empty())
{
nex[i] = 2000000000;
s.insert(a[i].y);
}
else
{
auto id = lower_bound(s.begin(), s.end(), a[i].y);
if (id == s.end())
nex[i] = 2000000000;
else
nex[i] = *id;
s.insert(a[i].y);
}
}
s.clear();
for (int i = mid + 1; i <= r; i++)
{
if (s.empty())
{
prv[i] = -2000000000;
s.insert(a[i].y);
}
else
{
auto id = upper_bound(s.begin(), s.end(), a[i].y);
if (id == s.begin())
prv[i] = -2000000000;
else
prv[i] = *prev(id);
s.insert(a[i].y);
}
b[i - mid] = {a[i].y, prv[i]};
}
int Nr = r - mid;
sort(b + 1, b + Nr + 1);
build(1, 1, Nr);
for (int i = l; i <= mid; i++)
{
int l_ = 1, r_ = r - mid, savL = -1, savR = -1, tg;
while (l_ <= r_)
{
tg = (l_ + r_) / 2;
if (b[tg].fi >= a[i].y)
{
savL = tg;
r_ = tg - 1;
}
else
l_ = tg + 1;
}
l_ = 1, r_ = r - mid;
while (l_ <= r_)
{
tg = (l_ + r_) / 2;
if (b[tg].fi <= nex[i])
{
savR = tg;
l_ = tg + 1;
}
else
r_ = tg - 1;
}
if (savL != -1 && savR != -1)
rs += get(1, 1, Nr, savL, savR, a[i].y);
}
dc(l, mid);
dc(mid + 1, r);
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1, [&](mix A, mix B)
{ return A.x < B.x; });
preST(1, 1, n);
dc(1, n);
cout << rs;
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... |