fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/saASFU
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!