Pagini recente » Cod sursa (job #2688828) | Cod sursa (job #599555) | Cod sursa (job #2252560) | Cod sursa (job #2251462) | Cod sursa (job #2376297)
#include <algorithm>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <utility>
#include <vector>
#define x first
#define y second
using namespace std;
ifstream fi("cadrane.in");
ofstream fo("cadrane.out");
using pii = pair<int, int>;
const int N = 1e5 + 5;
struct Nod {
int val, lazy; };
Nod pom[N * 4];
int v[N];
map<int, int> minmx;
vector<pii> pts;
int n, ql, qr, qval, bound, ant;
static void prop(int nod) {
pom[nod].val+= pom[nod].lazy;
pom[2 * nod].lazy+= pom[nod].lazy;
pom[2 * nod + 1].lazy+= pom[nod].lazy;
pom[nod].lazy = 0; }
static int eval(int nod) {
return pom[nod].val + pom[nod].lazy; }
static int query(int nod, int st, int dr) {
if (ql <= st && dr <= qr)
return eval(nod);
prop(nod);
int mid = (st + dr) / 2, ant = 1e9;
if (ql <= mid)
ant = min(ant, query(2 * nod, st, mid));
if (mid < qr)
ant = min(ant, query(2 * nod + 1, mid + 1, dr));
return ant; }
static void update(int nod, int st, int dr) {
if (ql <= st && dr <= qr) {
pom[nod].lazy+= qval;
return; }
prop(nod);
int mid = (st + dr) / 2;
if (ql <= mid)
update(2 * nod, st, mid);
if (mid < qr)
update(2 * nod + 1, mid + 1, dr);
pom[nod] = {min(eval(2 * nod), eval(2 * nod + 1)), 0}; }
static void normalize() {
map<int, int> mp;
int ptr = 0;
for (auto &i: pts)
mp[i.x] = 0;
for (auto &i: mp)
i.second = ++ptr;
for (auto &i: pts)
i.x = mp[i.x];
mp.clear();
ptr = 0;
for (auto &i: pts)
mp[i.y] = 0;
for (auto &i: mp)
i.second = ++ptr;
for (auto &i: pts)
i.y = mp[i.y]; }
int main() {
fi >> n;
pts.resize(n);
for (auto &p: pts) {
fi >> p.x >> p.y;
p.y = -p.y; }
normalize();
sort(begin(pts), end(pts));
for (auto p: pts)
bound = max(bound, p.y);
for (auto i: pts) {
ql = i.y, qr = bound;
qval = 1;
update(1, 1, bound); }
for (int dr = 0, st = 0; st < n; st = dr) {
for (; dr < n && pts[st].x == pts[dr].x; ++dr) {
ql = pts[dr].y, qr = bound;
qval = -1;
update(1, 1, bound); }
ant = max(ant, eval(1) + dr - st);
for (int i = st; i < dr; ++i) {
ql = 1, qr = pts[i].y;
qval = 1;
update(1, 1, bound); } }
fo << ant << endl;
return 0; }