fork(1) download
copy 
  1. #include <fstream>
  2. #include <complex>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <assert.h>
  6. #include <utility>
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <queue>
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <memory.h>
  13.  
  14. using namespace std;
  15.  
  16. int height[1 << 18];
  17. int minValue[1 << 18];
  18. int maxValue[1 << 18];
  19. int dx;
  20.  
  21. void Push(int pos)
  22. {
  23. 	if (pos >= dx)
  24. 		return;
  25.  
  26. 	if (height[pos] != 0)
  27. 	{
  28. 		height[pos * 2] = max(height[pos], height[pos * 2]);
  29. 		height[pos * 2 + 1] = max(height[pos], height[pos * 2 + 1]);
  30.  
  31. 		minValue[pos * 2] = max(minValue[pos * 2], height[pos]);
  32. 		maxValue[pos * 2] = max(maxValue[pos * 2],  height[pos]);
  33.  
  34. 		minValue[pos * 2 + 1] =  max(minValue[pos * 2 + 1], height[pos]);
  35. 		maxValue[pos * 2 + 1] =  max(maxValue[pos * 2 + 1], height[pos]);
  36.  
  37. 		height[pos] = 0;
  38. 	}
  39. }
  40. void SetSegment(int l, int r, int h, int pos, int tl, int tr)
  41. {
  42. 	Push(pos);
  43. 	if (l == tl && r == tr)
  44. 	{
  45. 		height[pos] = h;
  46. 		minValue[pos] = max(h, minValue[pos]);
  47. 		maxValue[pos] = max(h, maxValue[pos]);
  48. 		return;
  49. 	}
  50.  
  51. 	int m = (tl + tr) / 2;
  52.  
  53. 	if (r <= m)
  54. 		SetSegment (l, r, h, pos * 2, tl, m);
  55. 	else if (l >= m)
  56. 		SetSegment (l, r, h, pos * 2 + 1, m, tr);
  57. 	else
  58. 	{
  59. 		SetSegment (l, m, h, pos * 2, tl, m);
  60. 		SetSegment (m, r, h, pos * 2 + 1, m, tr);
  61. 	}
  62.  
  63. 	minValue[pos] = min(minValue[pos * 2 + 1], minValue[pos * 2]);
  64. 	maxValue[pos] = max(maxValue[pos * 2 + 1], maxValue[pos * 2]);
  65. }
  66.  
  67. int GetSegment(int l, int r, int h, int pos, int tl, int tr)
  68. {	
  69. 	Push(pos);
  70.  
  71. 	if (l == tl && r == tr)
  72. 	{
  73. 		if (minValue[pos] > h)
  74. 			return 0;
  75. 		if (maxValue[pos] <= h)		
  76. 			return r - l;
  77. 	}
  78. 	int m = (tl + tr) / 2;
  79.  
  80. 	if (r <= m)
  81. 		return GetSegment (l, r, h, pos * 2, tl, m);
  82. 	if (l >= m)
  83. 		return GetSegment (l, r, h, pos * 2 + 1, m, tr);
  84.  
  85. 	return GetSegment (l, m, h, pos * 2, tl, m) + GetSegment (m, r, h, pos * 2 + 1, m, tr);
  86. }
  87.  
  88. int main()
  89. {
  90. #ifndef ONLINE_JUDGE
  91. 	freopen("Test.in", "r", stdin);
  92. #endif
  93. 	int T;
  94. 	scanf("%d", &T);
  95.  
  96. 	while (T--)
  97. 	{
  98. 		int N;
  99. 		scanf("%d", &N);
  100.  
  101. 		dx = 1 << 17;
  102. 		memset(height, 0, sizeof(height));
  103.  
  104. 		memset(minValue, 0, sizeof(minValue));
  105. 		memset(maxValue, 0, sizeof(maxValue));
  106.  
  107. 		int ans = 0;
  108.  
  109. 		for (int i = 0; i < N; i++)
  110. 		{
  111. 			int l, r, h;
  112. 			scanf("%d %d %d", &l, &r, &h);
  113.  
  114. 			int res = GetSegment(l, r, h, 1, 0, dx);
  115.  
  116. 			SetSegment(l, r, h, 1, 0, dx);
  117.  
  118. 			ans += res;
  119. 		}
  120.  
  121. 		printf("%d\n", ans);
  122.  
  123. 	}
  124.  
  125. 	return 0;
  126. }
  127.  
stdin
copy 
1 
3 
5 11 3 
1 10 1 
3 13 2 
0
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:94: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:99: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:112: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
stdout
copy 
14
https://ideone.com/Njt4I
language:
C++ (gcc 8.3)
created:
13 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!