Cod sursa(job #994801)

Utilizator primulDarie Sergiu primul Data 6 septembrie 2013 13:12:23
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.32 kb
#include<stdio.h>
#include<algorithm>
 
#define maxn 100005
 
using namespace std;
 
FILE*f=fopen("cadrane.in","r");
FILE*g=fopen("cadrane.out","w");
 
int n,a,b;
int V[maxn],O[maxn],v2,o2,v,o;
int start[maxn];
 
struct pct{
    int x,y;
}A[maxn];
 
struct _arb{
    int ad;
    int min;
}Arb[4*maxn];
 
inline int cb ( int val , int *V , int N ){
    int p = 1,m,u = N;
     
    while ( p <= u ){
        m = (p+u)>>1;
        if ( V[m] == val )  return m;
        if ( V[m] > val )    u = m - 1;
        else    p = m + 1;
    }
     
    return 0;
}
 
inline void normalizare () {
     
    sort(V+1,V+v2+1);
    sort(O+1,O+o2+1);
     
    for ( int i = 1 ; i <= v2 ; ++i ){
        if ( i == 1 || V[i] != V[i-1] ){
            V[++v] = V[i];
        }
    }
    for ( int i = 1 ; i <= o2 ; ++i ){
        if ( i == 1 || O[i] != O[i-1] ){
            O[++o] = O[i];
        }
    }
     
    for ( int i = 1 ; i <= n ; ++i ){
        A[i].x = cb(A[i].x,V,v);
        A[i].y = cb(A[i].y,O,o);
    }
}
 
struct cmp1{
    inline bool operator () ( const pct &a , const pct &b ){
        return a.y < b.y;
    }
};
 
void init ( int nod , int st , int dr ){
     
    if ( st == dr ){
        Arb[nod].min = start[st];
        return ;
    }
     
    int mij = (st + dr)>>1;
    int nodst = nod << 1;
    int noddr = nodst + 1;
     
    init(nodst,st,mij);
    init(noddr,mij+1,dr);
     
    Arb[nod].min = min(Arb[nodst].min,Arb[noddr].min);
}
 
void update ( int nod , int st , int dr , int val ){
     
    if ( a <= st && dr <= b ){
        Arb[nod].ad += val;
        return ;
    }
     
    int mij = (st + dr)>>1;
    int nodst = nod << 1;
    int noddr = nodst + 1;
     
    Arb[nodst].ad += Arb[nod].ad;
    Arb[noddr].ad += Arb[nod].ad;
    Arb[nod].min += Arb[nod].ad; Arb[nod].ad = 0;
     
    if ( a <= mij ){
        update(nodst,st,mij,val);
    }
    if ( b > mij ){
        update(noddr,mij+1,dr,val);
    }
     
    Arb[nod].min = min(Arb[nodst].min+Arb[nodst].ad,Arb[noddr].min+Arb[noddr].ad);
}
 
struct cmp2{
    inline bool operator () ( const pct &a , const pct &b ){
        return a.x < b.x;
    }
};
 
int main () {
     
    fscanf(f,"%d",&n);
    for ( int i = 1 ; i <= n ; ++i ){
        fscanf(f,"%d %d",&A[i].x,&A[i].y);
        V[++v2] = A[i].x; O[++o2] = A[i].y;
    }
     
    normalizare();
     
    sort(A+1,A+n+1,cmp1());
     
    int p = n+1;
    for ( int i = o ; i >= 1 ; --i ){
        while ( p > 1 && A[p-1].y >= i ){
            --p;
        }
        start[i] = n-p+1;
    }
     
    init(1,1,o);
     
    sort(A+1,A+n+1,cmp2());
     
    int st=0,dr=0,sol=0;
    for ( int i = 1 ; i <= v ; ++i ){
        st = dr+1;
        while ( A[dr+1].x == i ){
            ++dr;
        }
         
        for ( int j = st ; j <= dr ; ++j ){
            a = A[j].y+1; b = o;
            if ( a <= b ){
                update(1,1,o,1);
            }
        }
         
        sol = max(sol,Arb[1].min+Arb[1].ad);
         
        for ( int j = st ; j <= dr ; ++j ){
            a = 1; b = A[j].y-1;
            if ( a <= b ){
                update(1,1,o,-1);
            }
        }
    }
     
    fprintf(g,"%d\n",sol);
     
    fclose(f);
    fclose(g);
     
    return 0;
}