Cod sursa(job #3253654)

Utilizator angelaAngela Visuian angela Data 4 noiembrie 2024 06:38:55
Problema Cadrane Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;
using PI = pair<int, int>;
#define x first 
#define y second
const int NMAX = 1e5 + 5;

ifstream fin("cadrane.in");
ofstream fout("cadrane.out");

int N, max_X, max_Y;
PI a[NMAX];
int st[4 * NMAX], lz[4 * NMAX];

void Propagate(int x, int l, int r) 
{
    if (lz[x])
    {
		st[x] += lz[x];
		if (l != r)
		{
			lz[2 * x] += lz[x];
			lz[2 * x + 1] += lz[x];
		}
		lz[x] = 0;
	}
}

void Update(int x, int l, int r, int L, int R, int val) 
{
    Propagate(x, l, r);
    if (L <= l && r <= R) 
    {
        lz[x] += val;
        Propagate(x, l, r);
        return;
    }

    int m = (l + r) / 2;
    if (L <= m) 
		Update(2 * x, l, m, L, R, val);
    if (R > m)  
		Update(2 * x + 1, m + 1, r, L, R, val);

    st[x] = min(st[2 * x], st[2 * x + 1]);
}

int main()
{
	fin >> N;
	for (int i = 1; i <= N; ++ i) 
		fin >> a[i].x >> a[i].y;
		
	map<int, int> mp;
	for (int i = 1; i <= N; ++i) 
		mp[a[i].x];

	for (auto [k, _] : mp) 
		mp[k] = ++max_X;

	for (int i = 1; i <= N; ++i) 
		a[i].x = mp[a[i].x];

	mp.clear();
	for (int i = 1; i <= N; ++i) 
		mp[a[i].y];

	for (auto [k, _] : mp) 
		mp[k] = ++max_Y;

	for (int i = 1; i <= N; ++i) 
		a[i].y = mp[a[i].y];

	sort(a + 1, a + N + 1);    

	for (int i = 1; i <= N; ++i) 
		Update(1, 1, max_Y, 1, a[i].y, 1);

	int ans = 0;

	for (int x = 1, i = 1; x <= max_X; ++x ) 
	{
		int j = i;
		while (j <= N && a[j].x == x) 
		{
			Update(1, 1, max_Y, a[j].y, max_Y, 1);
			++j;
		}

		ans = max(ans, st[1]);
		while (i <= N && a[i].x == x) 
		{
			Update(1, 1, max_Y, 1, a[i].y, -1);
			++i;
		}
	}

	fout << ans << '\n';

	return 0;
}