• Source
    1. /**************************************************************
    2.   Problem: 2276
    3.   User: zrts
    4.   Language: C++
    5.   Result: Accepted
    6.   Time:9300 ms
    7.   Memory:11444 kb
    8. ****************************************************************/
    9.  
    10. #include<cstdio>
    11. #include<cstring>
    12. #include<algorithm>
    13. #include<deque>
    14. //by zrt
    15. //problem:
    16. //
    17. using namespace std;
    18. typedef long long ll;
    19. const double eps(1e-10);
    20. const int inf(0x7fffffff);
    21. struct N{
    22. int x,w;
    23. N(int a=0,int b=0){
    24. x=a,w=b;
    25. }
    26. };
    27. deque<N> q;
    28. #define MAXN 1020000
    29. int n,tmin[MAXN],tmax[MAXN];
    30. int ans;
    31. int main(){
    32. #ifdef LOCAL
    33. freopen("in.txt","r",stdin);
    34. freopen("out.txt","w",stdout);
    35. #endif
    36. scanf("%d",&n);
    37. for(int i=1;i<=n;i++){
    38. scanf("%d%d",&tmin[i],&tmax[i]);
    39. }
    40. for(int i=1,a,b;i<=n;i++){
    41. a=tmin[i],b=tmax[i];
    42. int front=i;
    43. while(!q.empty() && q.front().w<=a){
    44. front=min(front,q.front().x);
    45. q.pop_front();
    46. }
    47. q.push_front(N(front,a));
    48. while(!q.empty() && q.back().w> b){
    49. ans=max(ans,i-q.back().x);
    50. q.pop_back();
    51. }
    52. }
    53. while(!q.empty()){
    54. ans=max(ans,n-q.back().x+1);
    55. q.pop_back();
    56. }
    57. printf("%d\n",ans);
    58. return 0;
    59. }