Pagini recente » Cod sursa (job #445985) | Cod sursa (job #3031053) | Cod sursa (job #1157754) | Cod sursa (job #461037) | Cod sursa (job #716206)
Cod sursa(job #716206)
#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;
}