fork(5) download
copy 
  1. #include <list>
  2. #include <set>
  3. #include <map>
  4. #include <ctime>
  5. #include <stack>
  6. #include <string>
  7. #include <vector>
  8. #include <cstdio>
  9. #include <cmath>
  10. #include <queue>
  11. #include <deque>
  12. #include <bitset>
  13. #include <cstdlib>
  14. #include <cctype>
  15. #include <cstring>
  16. #include <iterator>
  17. #include <cassert>
  18. #include <fstream>
  19. #include <numeric>
  20. #include <iomanip>
  21. #include <complex>
  22. #include <sstream>
  23. #include <iostream>
  24. #include <algorithm>
  25. using namespace std;
  26.  
  27. #define LL long long
  28. #define int64 LL
  29.  
  30. typedef vector < int > VI;
  31. typedef pair< int , int > pii;
  32. typedef pair < LL , LL > PLL;
  33. #define fr first
  34. #define se second
  35. #define pi M_PI
  36. #define rad(x) (x)*acos(-1)/180.0
  37. #define EPS 1e-6
  38. #define INF 10000*10000*10000LL
  39. stringstream ss;
  40. #define two(x) ( 1LL<<x )
  41. #define sq(x) ( (x)*(x) )
  42. LL mod = 1000000007LL;
  43.  
  44. /**************************Code****************************/
  45.  
  46. vector < int > a[10010];
  47. int all[20010], sz;
  48.  
  49. int main()
  50. {
  51. 	int t, n;
  52. 	cin >> t;
  53. 	while( t -- )
  54. 	{
  55. 		for( int i = 0 ; i < 10001 ; i ++ )
  56. 			a[i].clear();
  57. 		scanf( "%d" , &n );
  58. 		for( int i = 0 ; i < n ; i ++ )
  59. 		{
  60. 			int h, w;
  61. 			scanf( "%d%d" , &h , &w );
  62. 			a[h].push_back( w );
  63. 		}
  64. 		for( int i = sz = 0 ; i < 10001 ; i ++ )
  65. 			if( a[i].size() )
  66. 			{
  67. 				sort( a[i].begin() , a[i].end() , greater < int > () );
  68. 				int j = 0, k = 0;
  69. 				while( j < a[i].size() )
  70. 				{
  71. 					while( k < sz && all[k] >= a[i][j] )
  72. 						k ++;
  73. 					if( k == sz )
  74. 						all[ sz++ ] = a[i][j ++];
  75. 					else
  76. 						all[k] = a[i][j ++];
  77. 					k ++;
  78. 				}
  79. 			}
  80. 		printf( "%d\n" , sz );
  81. 	}
  82. 	return 0;
  83. }
  84.  
Success #stdin #stdout 0s 3544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/n2FrDc
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

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!