Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2019
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <deque>
  4.  
  5. using namespace std;
  6. ifstream fin("diagonala.in");
  7. ofstream fout("diagonala.out");
  8.  
  9. const int nmx=200005;
  10. int n,i,j,p,nr,rez,x1,x2,n1,n2;
  11.  
  12. struct Seg
  13. { int x,y; } filn[nmx],ln[nmx],qmx[nmx],qmn[nmx];
  14.  
  15. void add(Seg a,int id)
  16. {
  17. while(x1<=x2 && qmx[x2].x<a.x)
  18. x2--;
  19. qmx[++x2]={a.x, id};
  20.  
  21. while(n1<=n2 && qmn[n2].x>a.y)
  22. n2--;
  23. qmn[++n2]={a.y, id};
  24. }
  25. void erase(int id)
  26. {
  27. if(x1<=x2 && qmx[x1].y==id)
  28. x1++;
  29. if(n1<=n2 && qmn[n1].y==id)
  30. n1++;
  31. }
  32.  
  33. void solve()
  34. {
  35. x1=n1=1;
  36. x2=n2=0;
  37. p=1;
  38. add(ln[1],1);
  39. for(i=2;i<=n;i++)
  40. {
  41. add(ln[i], i);
  42. while(p<i && qmx[x1].x>qmn[n1].x)
  43. {
  44. erase(p);
  45. p++;
  46. }
  47. rez=max(rez, i-p+1);
  48. }
  49. }
  50.  
  51. int main() {
  52.  
  53. fin>>n;
  54. for(i=1;i<=n;i++)
  55. fin>>filn[i].x>>filn[i].y;
  56.  
  57. rez=1;
  58.  
  59. for(i=1;i<=n;i++)
  60. ln[i]={filn[i].x+(i-1), filn[i].y+(i-1)};
  61.  
  62. solve();
  63.  
  64. for(i=n;i>=1;i--)
  65. ln[i]={filn[i].x+(n-i), filn[i].y+(n-i)};
  66.  
  67. solve();
  68.  
  69. fout<<rez<<"\n";
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement