Cod sursa(job #3253653)

Utilizator angelaAngela Visuian angela Data 4 noiembrie 2024 06:37:08
Problema Cadrane Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 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;
}