Pagini recente » Cod sursa (job #519634) | Cod sursa (job #1946919) | Cod sursa (job #2702351) | Cod sursa (job #1729136) | Cod sursa (job #2048842)
#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;
}