fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. typedef long long LL;
  8.  
  9. inline int read()
  10. {
  11. 	int x = 0; int v = 1, c;
  12. 	while(c = getchar(), c < '0' || c > '9') if(c == '-') v = -1;
  13. 	for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  14. 	return x * v;
  15. }
  16.  
  17. const int maxn = 20005;
  18.  
  19. int n, cnt[maxn];
  20. vector<int> p;
  21. pair<int, int> data[maxn];
  22. int col[maxn << 2];
  23.  
  24. inline void pushdown(int o)
  25. {
  26. 	if(col[o]) {
  27. 		col[o << 1] = col[o << 1 | 1] = col[o];
  28. 		col[o] = 0;
  29. 	}
  30. }
  31.  
  32. void color(int o, int L, int R, int ql, int qr, int v)
  33. {
  34. 	if(L == ql && qr == R) {
  35. 		col[o] = v;
  36. 	} else {
  37. 		pushdown(o);
  38. 		int M = (L + R) >> 1;
  39. 		if(qr <= M) {
  40. 			color(o << 1, L, M, ql, qr, v);
  41. 		} else if(ql > M) {
  42. 			color(o << 1 | 1, M + 1, R, ql, qr, v);
  43. 		} else {
  44. 			color(o << 1, L, M, ql, M, v);
  45. 			color(o << 1 | 1, M + 1, R, M + 1, qr, v);
  46. 		}
  47. 	}
  48. }
  49.  
  50. int query(int o, int L, int R, int p)
  51. {
  52. 	if(L == R) {
  53. 		return col[o];
  54. 	} else {
  55. 		pushdown(o);
  56. 		int M = (L + R) >> 1;
  57. 		if(p <= M)
  58. 			return query(o << 1, L, M, p);
  59. 		else
  60. 			return query(o << 1 | 1, M + 1, R, p);
  61. 	}
  62. }
  63.  
  64. #define find(x) lower_bound(p.begin(), p.end(), x) - p.begin() + 1
  65.  
  66. void input()
  67. {
  68. 	register int x, y;
  69. 	p.clear();
  70. 	memset(cnt, 0, sizeof(cnt));
  71. 	memset(col, 0, sizeof(cnt));
  72.  
  73. 	n = read();
  74. 	for(int i = 0; i < n; ++i) {
  75. 		p.push_back(x = read());
  76. 		p.push_back(y = read());
  77. 		data[i] = make_pair(x, y);
  78. 	}
  79. 	sort(p.begin(), p.end());
  80. 	p.resize(unique(p.begin(), p.end()) - p.begin());
  81. }
  82.  
  83. void solve()
  84. {
  85. 	register int ans = 0;
  86. 	for(int i = 0; i < n; ++i)
  87. 		color(1, 1, p.size(), find(data[i].first), find(data[i].second), i);
  88. 	for(int i = 1; i <= int(p.size()); ++i) {
  89. 		int x = query(1, 1, p.size(), i);
  90. 		if(!cnt[x]) ans += (cnt[x] = 1);
  91. 	}
  92. 	printf("%d\n", ans);
  93. }
  94.  
  95. int main()
  96. {
  97. #ifndef ONLINE_JUDGE
  98. 	freopen("input.txt", "r", stdin);
  99. 	freopen("output.txt", "w", stdout);
  100. #endif
  101.  
  102. 	int T = read();
  103. 	while(T--) {
  104. 		input();
  105. 		solve();
  106. 	}
  107.  
  108. #ifndef ONLINE_JUDGE
  109. 	fclose(stdin), fclose(stdout);
  110. #endif
  111. 	return 0;
  112. }
Time limit exceeded #stdin #stdout 5s 3960KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ELtCnm
poj2528
language:
C++14 (clang 8.0)
created:
9 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!