Cod sursa(job #3350870)

Utilizator CarenaMironov Cezar Luca Carena Data 14 aprilie 2026 14:52:40
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
#define fr first
#define sc second

using namespace std;

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

const int NMAX=1e5;
int n, ans;
pair<int, int> v[NMAX+5];
int nnrmx, nnrmy;
map<int, int> nrmx, nrmy;
vector<int> adjx[NMAX+5];

int idx(int x)
{
    if(nrmx[x]==0)
        nrmx[x]=(++nnrmx);
    return nrmx[x];
}

int idy(int y)
{
    if(nrmy[y]==0)
        nrmy[y]=(++nnrmy);
    return nrmy[y];
}

struct AINT
{
    int aint[4*NMAX+5], lazy[4*NMAX+5];
    
    void propag(int nod)
    {
        if(lazy[nod]==0)
            return;
        aint[nod]+=lazy[nod];
        if(nod<=2*NMAX)
        {
            lazy[2*nod]+=lazy[nod];
            lazy[2*nod+1]+=lazy[nod];
        }
        lazy[nod]=0;
    }
    
    void update(int nod, int l, int r, int ul, int ur, int val)
    {
        propag(nod);
        if(ur<l || r<ul)
            return;
        if(ul<=l && r<=ur)
        {
            lazy[nod]+=val;
            propag(nod);
            return;
        }
        int mid=(l+r)/2;
        update(2*nod, l, mid, ul, ur, val);
        update(2*nod+1, mid+1, r, ul, ur, val);
        aint[nod]=min(aint[2*nod], aint[2*nod+1]);
    }
    
    int query()
    {
        propag(1);
        return aint[1];
    }
}ds;

int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i].sc>>v[i].fr;
    
    //norm y
    sort(v+1, v+n+1);
    for(int i=1;i<=n;i++)
    {
        v[i].fr=idy(v[i].fr);
        swap(v[i].fr, v[i].sc);
    }
    
    //norm x
    sort(v+1, v+n+1);
    for(int i=1;i<=n;i++)
    {
        v[i].fr=idx(v[i].fr);
        adjx[v[i].fr].push_back(v[i].sc);
        ds.update(1, 1, nnrmy, 1, v[i].sc, 1);
    }
    
    for(int x=1;x<=nnrmx;x++)
    {
        for(auto y:adjx[x])
            ds.update(1, 1, nnrmy, y, nnrmy, 1);
        
        ans=max(ans, ds.query());
        
        for(auto y:adjx[x])
            ds.update(1, 1, nnrmy, 1, y, -1);
    }
    out<<ans;
    return 0;
}