Pagini recente » Cod sursa (job #2286442) | Cod sursa (job #1030692) | Cod sursa (job #2026266) | Cod sursa (job #2927374) | Cod sursa (job #2096368)
#include <bits/stdc++.h>
#define MAXN 100000
struct Biggus{
int x, y;
} v[1 + MAXN];
bool cmp1(Biggus Dickus, Biggus Falus){
return Dickus.x < Falus.x;
};
bool cmp2(Biggus Dickus, Biggus Falus){
return Dickus.y < Falus.y;
};
int left, right, val;
int aint[4 * MAXN];
int lazy[4 * MAXN];
void update(int p, int st, int dr){
if(left <= st && dr <= right){
lazy[p] += val;
aint[p] += lazy[p];
if(st != dr){
lazy[2 * p] += lazy[p];
lazy[2 * p + 1] += lazy[p];
}
lazy[p] = 0;
}
else{
lazy[2 * p] += lazy[p];
lazy[2 * p + 1] += lazy[p];
lazy[p] = 0;
int m = (st + dr) / 2;
if(left <= m) update(2 * p, st, m);
if(m + 1 <= right) update(2 * p + 1, m + 1, dr);
aint[p] = std::min(aint[2 * p] + lazy[2 * p], aint[2 * p + 1] + lazy[2 * p + 1]);
}
}
int main(){
FILE*fi,*fo;
fi = fopen("cadrane.in","r");
fo = fopen("cadrane.out","w");
int n;
fscanf(fi,"%d", &n);
for(int i = 1; i <= n; i++)
fscanf(fi,"%d%d", &v[i].x, &v[i].y);
std::sort(v + 1, v + n + 1, cmp2);
int prev = -1;
for(int i = 1; i <= n; i++){
if(prev == v[i].y){
prev = v[i].y;
v[i].y = v[i - 1].y;
}
else{
prev = v[i].y;
v[i].y = v[i - 1].y + 1;
}
}
int last = v[n].y;
std::sort(v + 1, v + n + 1, cmp1);
for(int i = 1; i <= n; i++){
left = 1;
right = v[i].y;
val = 1;
update(1, 1, last);
}
int ind1 = 1, ind2;
int max = -1;
while(ind1 <= n){
ind2 = ind1;
while(ind2 <= n && v[ind2].x == v[ind1].x){
left = v[ind2].y;
right = last;
val = 1;
update(1, 1, last);
ind2++;
}
max = std::max(max, aint[1]);
ind2 = ind1;
while(ind2 <= n && v[ind2].x == v[ind1].x){
left = 1;
right = v[ind2].y;
val = -1;
update(1, 1, last);
ind2++;
}
ind1 = ind2;
}
fprintf(fo,"%d\n", max);
fclose(fi);
fclose(fo);
return 0;
}