Pagini recente » Cod sursa (job #1495380) | Cod sursa (job #841001) | Cod sursa (job #2519383) | Cod sursa (job #2269288) | Cod sursa (job #2399913)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
using namespace std;
ifstream fin("cadrane.in");
ofstream fout("cadrane.out");
using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
const int Inf = 0x3f3f3f3f;
struct Point{
int x, y;
bool operator < (const Point& p) const
{
return x < p.x;
}
};
#define mid ((l + r) / 2 - ( l + r < 0 && (l + r) % 2 ))
class SegmTree{
public:
SegmTree(int l, int r)
: l{l}, r{r}, val{0}, lazy{0},
left{nullptr}, right{nullptr}
{
if (l != r)
{
left = new SegmTree(l, mid);
right = new SegmTree(mid + 1, r);
}
}
void Update(int x, int y, int v)
{
Propagate();
if (x > y)
return;
if (r < x || l > y)
return;
if (x <= l && r <= y)
{
lazy = v;
Propagate();
return;
}
left->Update(x, y, v);
right->Update(x, y, v);
val = min(left->val, right->val);
}
int Query(int x, int y)
{
Propagate();
if (r < x || l > y)
return Inf;
if (x <= l && r <= y)
return val;
return min(left->Query(x, y), right->Query(x, y));
}
~SegmTree()
{
if (l != r)
{
delete left;
delete right;
}
}
private:
void Propagate()
{
if (!lazy)
return;
val += lazy;
if (l != r)
{
left->lazy += lazy;
right->lazy += lazy;
}
lazy = 0;
}
int l, r;
int val;
int lazy;
SegmTree *left, *right;
};
int N;
vector<Point> a;
VI dy, id;
map<int, VI> mp;
void ReadData();
void Solve();
int main()
{
ReadData();
Solve();
fin.close();
fout.close();
return 0;
}
void ReadData()
{
fin >> N;
a = vector<Point>(N);
for (int i = 0; i < N; ++i)
fin >> a[i].x >> a[i].y;
sort(a.begin(), a.end());
}
void Solve()
{
for (const Point& p : a)
dy.push_back(p.y);
sort(dy.begin(), dy.end());
dy.erase(unique(dy.begin(), dy.end()), dy.end());
int M{(int)dy.size()};
id = VI(N);
for (size_t i = 0; i < a.size(); ++i)
{
id[i] = find(dy.begin(), dy.end(), a[i].y) - dy.begin();
mp[a[i].x].push_back(i);
}
SegmTree st(0, M - 1);
for (size_t i = 0; i < a.size(); ++i)
{
st.Update(0, id[i], +1);
}
int ans{st.Query(0, M - 1)};
for (const auto& it : mp)
{
for (const int& i : it.second)
st.Update(id[i] + 1, M - 1, +1);
ans = max(ans, st.Query(0, M - 1));
for (const int& i : it.second)
st.Update(0, id[i] - 1, -1);
}
fout << ans << '\n';
}