Pagini recente » Cod sursa (job #920802) | Cod sursa (job #303878) | Cod sursa (job #3168591) | Cod sursa (job #1273215) | Cod sursa (job #467510)
Cod sursa(job #467510)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define Nmax 100100
#define x first
#define y second
int n;
pair <int, int> a[Nmax];
vector<int> coord;
int sum[Nmax*3]; //pentru suma elementelor
int prefix[Nmax*3]; //pentru prefixul de suma minima
inline int Min(int A, int B) {
return A < B ? A : B;
}
void update(int ind, int st, int dr, int poz, int val) {
if (poz < st || poz > dr)
return ;
if (st == dr) {
sum[ind] += val;
prefix[ind] = sum[ind];
return ;
}
int mij = (st+dr)/2;
if (poz <= mij)
update(ind*2 , st, mij , poz, val);
else
update(ind*2+1, mij+1, dr, poz, val);
sum[ind] = sum[ind*2] + sum[ind*2+1];
prefix[ind] = Min(prefix[ind*2], sum[ind*2] + prefix[ind*2+1]);
}
int main() {
freopen("cadrane.in" , "r", stdin );
freopen("cadrane.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &a[i].x, &a[i].y);
coord.push_back(a[i].y);
}
//sortez punctele dupa x
sort(a+1, a+n+1);
//normalizez y-ul
sort(coord.begin(), coord.end());
coord.erase(unique(coord.begin(), coord.end()), coord.end());
int N = coord.size();
for (int i = 1; i <= n; ++i) {
int Y = a[i].y;
a[i].y = 0;
for (int j = (1<<18); j > 0; j /= 2)
if (a[i].y + j < (int)coord.size() && coord[a[i].y + j] <= Y)
a[i].y += j;
++a[i].y;
}
//initializez arborele
for (int i = 1; i <= n; ++i)
update(1, 1, N, a[i].y + 1, -1);
//parcurg punctele pe x si fac_updateuri pe arborele de intervale
int last = 1, best = 0, pctA = n;
for (int i = 1; i <= n; ++i) {
last = i;
while (last < n && a[last+1].x == a[i].x)
++last;
//astea ajung pe axa si nu le mai scad
for (int j = i; j <= last; ++j) {
update(1, 1, N, a[j].y + 1, +1);
}
if (best < pctA + prefix[1])
best = pctA + prefix[1];
//acum astea sunt dupa axa si le adun
for (int j = i; j <= last; ++j) {
update(1, 1, N, a[j].y, +1);
--pctA;
}
i = last;
}
printf("%d\n", best);
return 0;
}