Cod sursa(job #2738310)

Utilizator stefantagaTaga Stefan stefantaga Data 5 aprilie 2021 17:52:33
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("cadrane.in");
ofstream g("cadrane.out");
int n,i,nr;
map <int,int> mx,my;
struct wow
{
    int x,y;
}v[100005];
bool compare (wow a,wow b)
{
    return a.x<b.x;
}
int arb[400005],lazy[400005];
void propag(int st,int dr,int nod)
{
    if (st==dr||lazy[nod]==0)
    {
        return ;
    }
    arb[2*nod]+=lazy[nod];
    arb[2*nod+1]+=lazy[nod];
    lazy[2*nod]+=lazy[nod];
    lazy[2*nod+1]+=lazy[nod];
    lazy[nod]=0;
}
int minim(int a,int b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}
void update (int st,int dr,int nod,int ua,int ub,int val)
{
    propag(st,dr,nod);
    if (ua<=st&&dr<=ub)
    {
        arb[nod]+=val;
        lazy[nod]+=val;
        return;
    }
    int mij=(st+dr)/2;
    if (ua<=mij)
    {
        update(st,mij,2*nod,ua,ub,val);
    }
    if (mij<ub)
    {
        update(mij+1,dr,2*nod+1,ua,ub,val);
    }
    arb[nod]=minim(arb[2*nod],arb[2*nod+1]);
}
int maxx,maxy,j,sol;
int main()
{
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
        mx[v[i].x]=1;
        my[v[i].y]=1;
    }
    nr=0;
    for (auto ind:mx)
    {
        nr++;
        mx[ind.first]=nr;
    }
    nr=0;
    for (auto ind:my)
    {
        nr++;
        my[ind.first]=nr;
    }
    for (i=1;i<=n;i++)
    {
        v[i].x=mx[v[i].x];
        v[i].y=my[v[i].y];
        maxy=max(maxy,v[i].y);
        maxx=max(maxx,v[i].x);
    }
    sort (v+1,v+n+1,compare);
    for (i=1;i<=n;i++)
    {
        update(1,maxy,1,1,v[i].y,1);
    }
    int cop,st=1;
    for (i=1;i<=maxx;i++)
    {
        cop=st;
        while (cop<=n&&v[cop].x==i)
        {
            update(1,maxy,1,v[cop].y,maxy,1);
            cop++;
        }
        sol=max(sol,arb[1]);
        while (st<=n&&v[st].x==i)
        {
            update(1,maxy,1,1,v[st].y,-1);
            st++;
        }
    }
    g<<sol;
    return 0;
}