Cod sursa(job #1554027)

Utilizator alexpetrescuPetrescu Alexandru alexpetrescu Data 20 decembrie 2015 20:26:34
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.26 kb
#include <cstdio>
#include <algorithm>
#include <cctype>
#define BUF_SIZE 4096
#define MAXN 100000
int n, u, v, pos=BUF_SIZE, ans, left, right, add, min[4*MAXN], lazy[4*MAXN], a[MAXN], b[MAXN], x[MAXN], y[MAXN], q[MAXN], lista[MAXN], next[MAXN+1];
char buf[BUF_SIZE];
FILE *fin;
inline int min2(int a, int b){
    if(a<b){
        return a;
    }
    return b;
}
inline char nextch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int read(){
    int x=0, s=1;
    char ch=nextch();
    while((!isdigit(ch))&&(ch!='-')){
        ch=nextch();
    }
    if(ch=='-'){
        s=-1;
        ch=nextch();
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return  s*x;
}
inline void norm(){
    int i, rez, pas;
    std::sort(a, a+n);
    std::sort(b, b+n);
    u=0;
    v=0;
    a[u++]=a[0];
    b[v++]=b[0];
    for(i=1; i<n; i++){
        if(a[u-1]!=a[i]){
            a[u++]=a[i];
        }
        if(b[v-1]!=b[i]){
            b[v++]=b[i];
        }
    }
    for(i=0; i<n; i++){
        rez=0;
        for(pas=1<<16; pas; pas>>=1){
            if((rez+pas<u)&&(a[rez+pas]<=x[i])){
                rez+=pas;
            }
        }
        x[i]=rez;
        next[i+1]=lista[rez];
        lista[rez]=i+1;
        rez=0;
        for(pas=1<<16; pas; pas>>=1){
            if((rez+pas<v)&&(b[rez+pas]<=y[i])){
                rez+=pas;
            }
        }
        y[i]=rez;
    }
}
void dfs(int p, int st, int dr){
    if(st==dr){
        lazy[p]=0;
        min[p]=q[st];
        return ;
    }
    int m=(st+dr)/2;
    dfs(2*p, st, m);
    dfs(2*p+1, m+1, dr);
    min[p]=min2(min[2*p], min[2*p+1]);
    lazy[p]=0;
}
void update(int p, int st, int dr){
    if((left<=st)&&(dr<=right)){
        lazy[p]+=add;
        min[p]+=add;
        return ;
    }
    int m=(st+dr)/2;
    if(lazy[p]){
        lazy[2*p]+=lazy[p];
        lazy[2*p+1]+=lazy[p];
        min[2*p]+=lazy[p];
        min[2*p+1]+=lazy[p];
        lazy[p]=0;
    }
    if(left<=m){
        update(2*p, st, m);
    }
    if(m+1<=right){
        update(2*p+1, m+1, dr);
    }
    min[p]=min2(min[2*p], min[2*p+1]);
}
inline void baga(int p){
    left=0;
    right=y[p];
    add=1;
    update(1, 0, v-1);
}
inline void scoate(int p){
    left=y[p];
    right=v-1;
    add=-1;
    if(left<=right){
        update(1, 0, v-1);
    }
}
int main(){
    int i, p;
    FILE *fout;
    fin=fopen("cadrane.in", "r");
    fout=fopen("cadrane.out", "w");
    n=read();
    for(i=0; i<n; i++){
        x[i]=read();
        y[i]=-read();
        a[i]=x[i];
        b[i]=y[i];
    }
    norm();
    for(i=0; i<n; i++){
        q[y[i]]++;
    }
    for(i=1; i<v; i++){
        q[i]+=q[i-1];
    }
    dfs(1, 0, v-1);
    for(i=0; i<u; i++){
        p=lista[i];
        while(p){
            baga(p-1);
            p=next[p];
        }
        if(i>0){
            p=lista[i-1];
            while(p){
                scoate(p-1);
                p=next[p];
            }
        }
        if(ans<min[1]){
            ans=min[1];
        }
    }
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}