Pagini recente » Cod sursa (job #1097153) | Cod sursa (job #2273514) | Cod sursa (job #41279) | Cod sursa (job #772952) | Cod sursa (job #1776528)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("cadrane.in");
ofstream cout("cadrane.out");
const int MAXN = 100000;
struct Point {
int x, y;
int index;
};
Point v[1 + MAXN];
int value[1 + MAXN + 1], limit;
bool CompareX(const Point &a, const Point &b) {
return a.x < b.x;
};
bool CompareY(const Point &a, const Point &b) {
return a.y < b.y;
};
void Normalize(int n) {
sort(v + 1, v + n + 1, CompareY);
value[v[1].index] = 1;
for (int i = 2; i <= n; i++) {
value[v[i].index] = value[v[i - 1].index];
if (v[i].y != v[i - 1].y)
value[v[i].index]++;
}
limit = value[v[n].index];
}
int tree[1 + 4 * MAXN], lazy[1 + 4 * MAXN];
void Update(int node, int left, int right, int leftIndex, int rightIndex, int add) {
if (right < leftIndex || rightIndex < left)
return;
if (leftIndex <= left && right <= rightIndex) {
lazy[node] += add;
return;
}
int middle = (left + right) / 2;
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
lazy[node] = 0;
if (leftIndex <= middle)
Update(2 * node, left, middle, leftIndex, rightIndex, add);
if (middle + 1 <= rightIndex)
Update(2 * node + 1, middle + 1, right, leftIndex, rightIndex, add);
tree[node] = min(tree[2 * node] + lazy[2 * node], tree[2 * node + 1] + lazy[2 * node + 1]);
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i].x >> v[i].y;
v[i].index = i;
}
Normalize(n);
sort(v + 1, v + n + 1, CompareX);
for (int i = 1; i <= n; i++)
Update(1, 1, limit, 1, value[v[i].index], 1);
int j = 1;
int answer = 0;
for (int i = 1; i <= n; i++) {
Update(1, 1, limit, value[v[i].index], limit, 1);
if (v[i].x != v[i + 1].x) {
answer = max(answer, tree[1] + lazy[1]);
while (j <= i) {
Update(1, 1, limit, 1, value[v[j].index], -1);
j++;
}
}
}
cout << answer << "\n";
return 0;
}