Pagini recente » Cod sursa (job #2704065) | Cod sursa (job #1434439) | Cod sursa (job #1485814) | Cod sursa (job #457819) | Cod sursa (job #2632187)
#include <fstream>
#include <algorithm>
#include <map>
#define x first
#define y second
using namespace std;
typedef pair <int, int> PI;
constexpr int NMAX = 1e5 + 5;
ifstream f ("cadrane.in");
ofstream g ("cadrane.out");
int N, Max_X, Max_Y;
PI a[NMAX];
int arb[4 * NMAX], lazy[4 * NMAX];
void Propag (int nod, int a, int b) {
if (a == b) return;
if (lazy[ nod ] == 0) return;
lazy[2 * nod] += lazy[ nod ];
lazy[2 * nod + 1] += lazy[ nod ];
arb[2 * nod] += lazy[ nod ];
arb[2 * nod + 1] += lazy[ nod ];
lazy[ nod ] = 0;
}
void Update (int nod, int a, int b, int ua, int ub, int val) {
Propag(nod, a, b);
if (ua <= a && b <= ub) {
arb[ nod ] += val;
lazy[ nod ] += val;
return;
}
int mij = (a + b) / 2;
if (ua <= mij) Update(2 * nod, a, mij, ua, ub, val);
if (mij < ub) Update(2 * nod + 1, mij + 1, b, ua, ub, val);
arb[ nod ] = min(arb[ 2 * nod], arb[ 2 * nod + 1]);
}
void Read () {
f >> N;
for (int i = 1; i <= N; ++ i ) {
f >> a[ i ].x >> a[ i ].y;
}
}
void NormalizareAndSortare () {
map <int, int> mp;
for (int i = 1; i <= N; ++ i ) {
mp[a[ i ].x] = 1;
}
for (auto &it : mp) {
it.second = ++Max_X;
}
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] = 1;
}
for (auto &it : mp) {
it.second = ++Max_Y;
}
for (int i = 1; i <= N; ++ i ) {
a[ i ].y = mp[a[ i ].y];
}
sort(a+1, a+N+1);
}
void Solve () {
for (int i = 1; i <= N; ++ i ) {
Update(1, 1, Max_Y, 1, a[ i ].y, 1);
}
int ind = 1;
int ans = 0;
for (int i = 1; i <= Max_X; ++ i ) {
int aux = ind;
while (aux <= N && a[ aux ].x == i) {
Update(1, 1, Max_Y, a[ aux ].y, Max_Y, 1);
++ aux;
}
ans = max(ans, arb[1]);
while (ind <= N && a[ ind ].x == i) {
Update(1, 1, Max_Y, 1, a[ ind ].y, -1);
++ ind;
}
}
g << ans << '\n';
}
int main()
{
Read ();
NormalizareAndSortare ();
Solve ();
return 0;
}