Pagini recente » Cod sursa (job #781045) | Cod sursa (job #206482) | Cod sursa (job #810364) | Cod sursa (job #1668911) | Cod sursa (job #2508927)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using VI = std::vector<int>;
using VVI = std::vector<VI>;
using VB = std::vector<bool>;
struct Point{
Point() : x{0}, y{0}
{}
Point(int x, int y) : x{x}, y{y}
{}
int x, y;
bool operator < (const Point& p) const
{
return x < p.x || (x == p.x && y < p.y);
}
};
class SegmTree{
public:
SegmTree(int x, int y)
: x{x}, y{y}, val{0}, lazy{0},
left{nullptr}, right{nullptr}
{
if (x != y)
{
int mid = (x + y) / 2;
left = new SegmTree(x, mid);
right = new SegmTree(mid + 1, y);
}
}
void Update(int begin, int end, int val)
{
Propagate();
if (end < x || begin > y)
return;
if (begin <= x && y <= end)
{
lazy = val;
Propagate();
return;
}
left->Update(begin, end, val);
right->Update(begin, end, val);
this->val = std::min(left->val, right->val);
}
int GetMinimum()
{
Propagate();
return val;
}
~SegmTree()
{
delete left;
delete right;
}
private:
void Propagate()
{
val += lazy;
if (x != y)
{
left->lazy += lazy;
right->lazy += lazy;
}
lazy = 0;
}
int x, y;
int val;
int lazy;
SegmTree *left, *right;
};
std::ifstream fin("cadrane.in");
std::ofstream fout("cadrane.out");
int N;
std::vector<Point> p, a;
VI cx, cy;
void ReadData();
void Solve();
void NormalizePoints();
void WritePoints(const std::vector<Point>& p);
int main()
{
ReadData();
Solve();
fin.close();
fout.close();
return 0;
}
void ReadData()
{
fin >> N;
p = std::vector<Point>(N);
for (int i = 0; i < N; ++i)
fin >> p[i].x >> p[i].y;
}
void Solve()
{
NormalizePoints();
std::sort(a.begin(), a.end());
int cnt_px0{0};
SegmTree st(0, cy.size() - 1);
for (const Point& p : a)
{
if (p.x == 0)
{
++cnt_px0;
continue;
}
st.Update(0, p.y, +1);
}
int ymax = static_cast<int>(cy.size() - 1);
int res = cnt_px0 + st.GetMinimum();
int i{0};
while (i < N && a[i].x == a[0].x)
++i;
for (; i < N; ++i)
{
int j{i - 1};
while (j >= 0 && a[j].x == a[i - 1].x)
{
st.Update(a[j].y, ymax, +1);
--j;
}
int cnt{1};
st.Update(0, a[i].y, -1);
while (i + 1 < N && a[i + 1].x == a[i].x)
{
++i; ++cnt;
st.Update(0, a[i].y, -1);
}
res = std::max(res, st.GetMinimum() + cnt);
}
fout << res << '\n';
}
void NormalizePoints()
{
for (const Point& pt : p)
{
cx.emplace_back(pt.x);
cy.emplace_back(pt.y);
}
std::sort(cx.begin(), cx.end());
std::sort(cy.begin(), cy.end());
cx.erase(unique(cx.begin(), cx.end()), cx.end());
cy.erase(unique(cy.begin(), cy.end()), cy.end());
for (const Point& pt : p)
{
int x = std::find(cx.begin(), cx.end(), pt.x) - cx.begin();
int y = std::find(cy.begin(), cy.end(), pt.y) - cy.begin();
a.emplace_back(x, y);
}
//WritePoints(a);
}
void WritePoints(const std::vector<Point>& p)
{
for (const Point& pt : p)
{
std::cout << pt.x << ' ' << pt.y << '\n';
}
}