fork download
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <utility>
  7. #include <set>
  8. #include <map>
  9. #include <ctime>
  10. #include <queue>
  11. #include <cmath>
  12. #include <list>
  13. #include <assert.h>
  14.  
  15. using namespace std;
  16.  
  17. typedef long long ll;
  18. typedef long double ld;
  19. typedef unsigned long long ull;
  20.  
  21. #define f first
  22. #define s second
  23. #define pb push_back
  24. #define mp make_pair
  25.  
  26. const int maxn = 300500;
  27. const int inf = 1e9;
  28. const double eps = 1e-8;
  29. const int base = 1073676287;
  30.  
  31. struct node {
  32. int prior, sz, dp, add;
  33. node *l, *r;
  34. node ( int x ) {
  35. prior = ( rand() << 15 ) | rand();
  36. // sz = 1;
  37. dp = x;
  38. l = r = NULL;
  39. add = 0;
  40. }
  41. };
  42.  
  43. typedef node * pnode;
  44.  
  45. // int getSize( pnode T ) {
  46. // return T ? T -> sz : 0;
  47. // }
  48.  
  49. void push( pnode T ) {
  50. T -> dp += T -> add;
  51. if ( T -> l )
  52. T -> l -> add += T -> add;
  53. if ( T -> r )
  54. T -> r -> add += T -> add;
  55. T -> add = 0;
  56. }
  57.  
  58. void merge( pnode &T, pnode L, pnode R ) {
  59. if ( !L ) {
  60. T = R;
  61. return;
  62. }
  63. if ( !R ) {
  64. T = L;
  65. return;
  66. }
  67. if ( L -> prior > R -> prior ) {
  68. push( L );
  69. merge( L -> r, L -> r, R );
  70. T = L;
  71. // T -> sz = getSize( T -> l ) + getSize( T -> r ) + 1;
  72. return;
  73. }
  74. push( R );
  75. merge( R -> l, L, R -> l );
  76. T = R;
  77. // T -> sz = getSize( T -> l ) + getSize( T -> r ) + 1;
  78. }
  79.  
  80. void split( pnode T, int value, pnode &L, pnode &R ) {
  81. if ( !T ) {
  82. L = R = NULL;
  83. return;
  84. }
  85. push( T );
  86. if ( T -> dp >= value ) {
  87. split( T -> l, value, L, T -> l );
  88. R = T;
  89. // R -> sz = 1 + getSize( R -> l ) + getSize( R -> r );
  90. return;
  91. }
  92. split( T -> r, value, T -> r, R );
  93. L = T;
  94. // L -> sz = 1 + getSize( L -> l ) + getSize( T -> r );
  95. }
  96.  
  97. int findBegin( pnode T ) {
  98. push( T );
  99. if ( !T -> l )
  100. return T -> dp;
  101. return findBegin( T -> l );
  102. }
  103.  
  104. int findMax( pnode T, int n ) {
  105. if ( !T )
  106. return 0;
  107. push( T );
  108. return findMax( T -> l, n ) + findMax( T -> r, n ) + ( T -> dp <= inf ? 1 : 0 );
  109. }
  110.  
  111. void printTree( pnode T ) {
  112. if ( !T )
  113. return;
  114. push( T );
  115. printTree( T -> l );
  116. printf ( "%d ", T -> dp );
  117. printTree( T -> r );
  118. }
  119.  
  120. pair < int, int > a[maxn];
  121. pnode T = new node( 0 );
  122. pnode L = NULL;
  123. pnode M = NULL;
  124. pnode R = NULL;
  125. pnode rubbish = NULL;
  126.  
  127. void solve() {
  128. int n;
  129. scanf ( "%d", &n );
  130. for ( int j = 1; j <= n; j++ )
  131. scanf ( "%d%d", &a[j].f, &a[j].s );
  132. for ( int j = 1; j <= n; j++ )
  133. merge( T, T, new node( inf + j ) );
  134. // printTree(T);
  135. for ( int j = 1; j <= n; j++ ) {
  136. split( T, a[j].f, L, R );
  137. split( R, a[j].s, M, R );
  138. // printTree(M);
  139. // exit(0);
  140. if ( M )
  141. M -> add += 1;
  142. // printTree();
  143. int cnt = findBegin( R );
  144. split( R, cnt + 1, rubbish, R );
  145. merge( T, L, new node( a[j].f ) );
  146. merge( T, T, M );
  147. merge( T, T, R );
  148. }
  149. printf ( "%d\n", findMax( T, n ) - 1 );
  150. }
  151.  
  152.  
  153. int main()
  154.  
  155. {
  156. srand( time( NULL ) );
  157. // ios_base::sync_with_stdio( false );
  158. solve();
  159. return 0;
  160. }
  161.  
Success #stdin #stdout 0s 19424KB
stdin
Standard input is empty
stdout
0