Cod sursa(job #2048843)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 26 octombrie 2017 17:01:00
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include<cstdio>
using namespace std;
const int N=200001;
int av[N],bv[N],a[N],b[N],dmax[N],dmin[N];
int n;
int eliza_stiu_ca_te_uiti(int dir)
{
    int stmax=1,stmin=1,drmax=1,drmin=1,i,j=1,maxi=1;
    dmax[1]=dmin[1]=1;
    for(i=1; i<=n; i++)
    {
        a[i]=av[i]+i*dir;
        b[i]=bv[i]+i*dir;
    }
    for(i=2; i<=n; i++)
    {
        while(stmax<=drmax && a[i]>=a[dmax[drmax]])
            drmax--;
        dmax[++drmax]=i;
        while(stmin<=drmin && b[i]<=b[dmin[drmin]])
            drmin--;
        dmin[++drmin]=i;
        while(stmin<=drmin && stmax<=drmax && a[dmax[stmax]] > b[dmin[stmin]])
        {
            if(j==dmax[stmax])
                stmax++;
            if(j==dmin[stmin])
                stmin++;
            j++;
        }
        if(a[dmax[stmax]]<=b[dmin[stmin]])
            maxi=max(maxi,i-j+1);
    }
    return maxi;
}

int main()
{
    int i;
    FILE*fin,*fout;
    fin=fopen("diagonala.in","r");
    fout=fopen("diagonala.out","w");
    fscanf(fin,"%d",&n);
    for(i=1; i<=n; i++)
    {
        fscanf(fin,"%d%d",&av[i],&bv[i]);
    }
    int max1;
    max1=eliza_stiu_ca_te_uiti(1);
    max1=max(max1,eliza_stiu_ca_te_uiti(-1));
    fprintf(fout,"%d",max1);
    return 0;
    return 0;
}