Cod sursa(job #716206)

Utilizator CrescentselectJicol Crescent Crescentselect Data 18 martie 2012 14:12:05
Problema Cautare binara Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>

using namespace std;



ifstream in("diagonala.in");
ofstream out("diagonala.out");

int lmin,stmin,lmax,y[200022],x[200022],dmin[200022],dmax[200022],n,rezmax,a[200022],b[200022];

inline bool emptymin()
{
    return lmin>=stmin;
}

inline bool emptymax()
{
    return lmax;
}


void adaugamin(int poz)
{
    while(!emptymin() && y[dmin[lmin]]>=y[poz])
    {
        --lmin;
    }
    dmin[++lmin]=poz;
}

void adaugamax(int poz)
{
    while(!emptymax() && x[dmax[lmax]]>=y[poz])
    {
        --lmax;
    }
    dmax[++lmax]=poz;
}

inline bool vid()
{
    if(y[dmin[stmin]]<x[dmax[1]])
        return true;
    return false;
}

void scoate()
{
    stmin++;
}


void functie()
{
    int p=1,i;
    for(i=1;i<=n;++i)
    {
        adaugamin(i);
        adaugamax(i);
        while(!emptymin() && !emptymax() && vid())
        {
            ++p;
            scoate();
        }
        if (p-i+1>rezmax)
            rezmax=p-i+1;
    }
}


int main()
{
    int i;
    in>>n;
    for(i=1;i<=n;++i)
    {
        in>>a[i]>>b[i];
    }
    for(i=1;i<=n;++i)
    {
        x[i]=a[i]-i+1;
        y[i]=b[i]-i+1;
    }
    functie();
    for(i=1;i<=n;++i)
    {
        x[i]=a[i]+i-1;
        y[i]=b[i]+i-1;
    }
    functie();
    out<<rezmax;
    return 0;
}