Cod sursa(job #1741259)

Utilizator Bodo171Bogdan Pop Bodo171 Data 13 august 2016 14:44:11
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct node
{
    int val,add;
}arb[400005];
struct tip
{
    int x,y,ind;
}v[100005];
bool comp1(tip unu,tip doi)
{
    return unu.y<doi.y;
}
bool comp2(tip unu,tip doi)
{
    return unu.x<doi.x;
}
int i,n,m,mx,j,newcord[100005],nmax;
void update(int nod,int l,int r,int st,int dr,int value)
{
    if(st<=l&&r<=dr)
    {
        arb[nod].add+=value;
        return;
    }
    int m=(l+r)/2;
    if(arb[nod].add!=0)
    {
        update(2*nod,l,m,l,m,arb[nod].add);
        update(2*nod+1,m+1,r,m+1,r,arb[nod].add);
        arb[nod].add=0;
    }
    if(st<=m) update(2*nod,l,m,st,dr,value);
    if(m<dr) update(2*nod+1,m+1,r,st,dr,value);
    arb[nod].val=min(arb[2*nod].val+arb[2*nod].add,arb[2*nod+1].val+arb[2*nod+1].add);
}
int main()
{
    ifstream f("cadrane.in");
    ofstream g("cadrane.out");
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
        v[i].ind=i;
    }
    sort(v+1,v+n+1,comp1);
    newcord[v[1].ind]=1;
    for(i=2;i<=n;i++)
    {
        newcord[v[i].ind]=newcord[v[i-1].ind];
        if(v[i].y!=v[i-1].y) newcord[v[i].ind]++;
    }
    nmax=newcord[v[n].ind];
    sort(v+1,v+n+1,comp2);
    for(i=1;i<=n;i++)
    {
        update(1,1,nmax,1,newcord[v[i].ind],1);
    }
    j=1;
    for(i=1;i<=n;i++)
    {
        update(1,1,nmax,newcord[v[i].ind],nmax,1);
        if(v[i].x!=v[i+1].x)
        {
            if(arb[1].val+arb[1].add>mx) mx=arb[1].val+arb[1].add;
            while(j<=i)
            {
                update(1,1,nmax,1,newcord[v[j].ind],-1);
                j++;
            }
        }
    }
    g<<mx;
    return 0;
}