Pagini recente » Cod sursa (job #1399202) | Cod sursa (job #1142853) | Cod sursa (job #2812738) | Cod sursa (job #1000102) | Cod sursa (job #2399935)
#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;
map<int, int> m;
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()
{
id = VI(N);
for (size_t i = 0; i < a.size(); ++i)
{
mp[a[i].x].push_back(i);
m[a[i].y] = 0;
}
int M{0};
for (auto& p : m)
p.second = ++M;
SegmTree st(1, M);
for (size_t i = 0; i < a.size(); ++i)
{
st.Update(1, m[a[i].y], +1);
// cout << 1 << ' ' << m[a[i].y]; cin.get();
}
int ans{st.Query(1, M)};
for (const auto& it : mp)
{
for (const int& i : it.second)
st.Update(m[a[i].y] + 1, M, +1);
ans = max(ans, st.Query(1, M));
for (const int& i : it.second)
st.Update(1, m[a[i].y] - 1, -1);
}
fout << ans << '\n';
}