Pagini recente » Cod sursa (job #2781164) | Cod sursa (job #2248079) | Cod sursa (job #2172029) | Cod sursa (job #589851) | Cod sursa (job #2461631)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 1e5;
vector <int> v[1 + N];
struct Point {
int x;
int y;
};
Point a[1 + N];
int seg[1 + 4 * N], lazy[1 + 4 * N];
int nx, ny;
int n;
void norm ()
{
map <int, int> mp;
for (int i = 1; i <= n; i++)
mp[a[i].x] = 0;
nx = 0;
for (auto &x : mp)
x.second = ++nx;
for (int i = 1; i <= n; i++)
a[i].x = mp[a[i].x];
mp.clear ();
for (int i = 1; i <= n; i++)
mp[a[i].y] = 0;
ny = 0;
for (auto &x : mp)
x.second = ++ny;
for (int i = 1; i <= n; i++)
a[i].y = mp[a[i].y];
for (int i = 1; i <= n; i++)
v[a[i].x].pb (a[i].y);
}
void push (int node)
{
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
lazy[node] = 0;
}
void update (int node, int l, int r, int nl, int nr, int val)
{
if (nl <= l && r <= nr)
{
lazy[node] += val;
return;
}
push (node);
int mid = (l + r) / 2;
if (mid < nr)
update (node * 2 + 1, mid + 1, r, nl, nr, val);
if (mid >= nl)
update (node * 2, l, mid, nl, nr, val);
seg[node] = min (seg[node * 2] + lazy[node * 2], seg[node * 2 + 1] + lazy[node * 2 + 1]);
}
void update (int l, int r, int val)
{
update (1, 1, ny, l, r, val);
}
int best ()
{
return seg[1] + lazy[1];
}
int main()
{
freopen ("cadrane.in", "r", stdin);
freopen ("cadrane.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].x >> a[i].y;
norm ();
for (int i = 1; i <= n; i++)
update (1, a[i].y, 1);
int ans = 0;
for (int i = 1; i <= nx; i++)
{
for (auto it : v[i])
update (it, ny, 1);
for (auto it : v[i - 1])
update (1, it, -1);
ans = max (ans, best ());
}
cout << ans << "\n";
return 0;
}