Cod sursa(job #1897194)

Utilizator catalinrebegeaUNIBUC-Claudia Catarig catalinrebegea Data 1 martie 2017 11:28:18
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <bits/stdc++.h>
#define pii pair <int,int>
#define fi first
#define se second
#define Nmax 100005

using namespace std;

pii a[Nmax];
int n,v[Nmax],N,aint[4*Nmax],lazy[4*Nmax];
unordered_map <int,int> M;

inline void Normalize()
{
    int i;
    sort(v+1,v+n+1);
    M[v[1]]=1;
    for(i=2;i<=n;++i)
        M[v[i]]=M[v[i-1]]+(v[i]>v[i-1]);
    N=M[v[n]];
}

inline void propag(int nod)
{
    if(!lazy[nod]) return;
    aint[2*nod]+=lazy[nod]; lazy[2*nod]+=lazy[nod];
    aint[2*nod+1]+=lazy[nod]; lazy[2*nod+1]+=lazy[nod];
    lazy[nod]=0;
}

inline void upd(int nod, int st, int dr, int x, int y, int val)
{
    if(st==x && y==dr)
    {
        lazy[nod]+=val;
        aint[nod]+=val;
        return;
    }
    propag(nod);
    int mij=((st+dr)>>1);
    if(y<=mij) upd(2*nod,st,mij,x,y,val);
    else
        if(x>mij) upd(2*nod+1,mij+1,dr,x,y,val);
        else
        {
            upd(2*nod,st,mij,x,mij,val);
            upd(2*nod+1,mij+1,dr,mij+1,y,val);
        }
    aint[nod]=min(aint[2*nod],aint[2*nod+1]);
}

int main()
{
    int i,sol=0;
    ifstream cin("cadrane.in");
    ofstream cout("cadrane.out");
    cin>>n;
    for(i=1;i<=n;++i)
    {
        cin>>a[i].fi>>a[i].se;
        v[i]=a[i].se;
    }
    sort(a+1,a+n+1);

    Normalize();

    for(i=1;i<=n;++i) upd(1,1,N,1,M[a[i].se],1);

    int p1=0,p2=1;
    for(i=1;i<=n;++i)
    {
        for(;p1<n && a[p1+1].fi<=a[i].fi;)
            upd(1,1,N,M[a[++p1].se],N,1);

        for(;p2<=n && a[p2].fi<a[i].fi;)
            upd(1,1,N,1,M[a[p2++].se],-1);

        sol=max(sol,aint[1]);
    }

    cout<<sol<<"\n";
    return 0;
}