Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <deque>
- using namespace std;
- ifstream fin("diagonala.in");
- ofstream fout("diagonala.out");
- const int nmx=200005;
- int n,i,j,p,nr,rez,x1,x2,n1,n2;
- struct Seg
- { int x,y; } filn[nmx],ln[nmx],qmx[nmx],qmn[nmx];
- void add(Seg a,int id)
- {
- while(x1<=x2 && qmx[x2].x<a.x)
- x2--;
- qmx[++x2]={a.x, id};
- while(n1<=n2 && qmn[n2].x>a.y)
- n2--;
- qmn[++n2]={a.y, id};
- }
- void erase(int id)
- {
- if(x1<=x2 && qmx[x1].y==id)
- x1++;
- if(n1<=n2 && qmn[n1].y==id)
- n1++;
- }
- void solve()
- {
- x1=n1=1;
- x2=n2=0;
- p=1;
- add(ln[1],1);
- for(i=2;i<=n;i++)
- {
- add(ln[i], i);
- while(p<i && qmx[x1].x>qmn[n1].x)
- {
- erase(p);
- p++;
- }
- rez=max(rez, i-p+1);
- }
- }
- int main() {
- fin>>n;
- for(i=1;i<=n;i++)
- fin>>filn[i].x>>filn[i].y;
- rez=1;
- for(i=1;i<=n;i++)
- ln[i]={filn[i].x+(i-1), filn[i].y+(i-1)};
- solve();
- for(i=n;i>=1;i--)
- ln[i]={filn[i].x+(n-i), filn[i].y+(n-i)};
- solve();
- fout<<rez<<"\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement