# Cod sursa(job #2508724)

Utilizator Data 12 decembrie 2019 20:54:25 Cadrane 0 cpp-64 done Arhiva de probleme 2.49 kb
``````#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

#define x first
#define y second

using VI = vector<int>;
using PI = pair<int, int>;
using PPI = pair<int, PI>;
using VPI = vector<PI>;
using VPPI = vector<PPI>;
using VVI = vector<VI>;

int n, ny, nx;
VPI coord;
VI arb, lazy;
VVI a;

bool compy(const PI& A, const PI& B)
{
return A.y < B.y;
}

void normalizare();
void update(int, int, int, int, int, int);
void push(int, int, int);

int main()
{
normalizare();

arb = VI(4 * ny + 1);
lazy = VI(4 * ny + 1);

for (int i = 1; i <= n; ++ i)
update(1, 1, ny, 1, coord[i].y, 1);

int rez = 0;
for (int i = 0; i < nx; ++ i)
{
for (int j = 0; j < a[i].size(); j ++)
update(1, 1, ny, coord[i].y, ny, 1);
if (i != 0)
for (int j = 0; j < a[i - 1].size(); j ++)
update(1, 1, ny, coord[i - 1].y, ny, -1);

rez = max(arb[1], rez);
}

cout << rez;
return 0;
}
void normalizare()
{
cin >> n;
coord = VPI(n + 1);
for (int i = 1; i <= n; ++ i)
cin >> coord[i].x >> coord[i].y;

sort(coord.begin() + 1, coord.end(), compy);

int aux = 0;
for (int i = 1; i <= n; ++ i)
if (coord[i].y != aux || i == 1)
{
aux = coord[i].y;
coord[i].y = ++ ny;
}
else coord[i].y = ny;

sort(coord.begin() + 1, coord.end());

for (int i = 1; i <= n;)
{
a.push_back(VI());

aux = coord[i].x;
while (coord[i].x == aux)
{
a.back().push_back(coord[i].y);
++ i;
}
}

nx = a.size();
}
void update(int node, int st, int dr, int L, int R, int val)
{
if (L <= st && dr <= R)
{
arb[node] += val;
lazy[node] += val;
return;
}

if (lazy[node])push(node, st, dr);

int mijl = (st + dr)/2;
if (L <= mijl)update(2 * node, st, mijl, L, R, val);
if (R > mijl)update(2 * node + 1, mijl + 1, dr, L, R, val);

arb[node] = min(arb[2 * node], arb[2 * node + 1]);
}

void push(int node, int st, int dr)
{
if (st == dr)
{
lazy[node] = 0;
return;
}

lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];

arb[2 * node] += lazy[node];
arb[2 * node + 1] += lazy[node];

lazy[node] = 0;

}
``````