fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n, q;
  4. struct sec
  5. {
  6. 	int l, r;
  7. };
  8. sec merge(sec a, sec b)
  9. {
  10. 	sec c;
  11. 	c.l = min(a.l, b.l);
  12. 	c.r = max(a.r, b.r);
  13. 	return c;
  14. }
  15. struct node
  16. {
  17. 	int id, k, ls, rs;
  18. 	sec sc;
  19. };
  20. node a[200010];
  21. vector <int> e[200010];
  22. int fa[200010];
  23. void find_lr(int x)
  24. {
  25. 	for (auto y : e[x])
  26. 		if (y != fa[x])
  27. 			find_lr(y);
  28. 	sec now;
  29. 	if (x == 1)
  30. 		now = (sec){-2000000000, 2000000000};
  31. 	else
  32. 		now = (sec){a[x].k, a[x].k};
  33. 	for (auto y : e[x])
  34. 		if (y != fa[x])
  35. 			now = merge(now, a[y].sc);
  36. 	a[x].sc = now;
  37. }
  38. bool check(sec a, sec b)
  39. {
  40. 	if (b.l <= a.l && a.r <= b.r)
  41. 		return 0;
  42. 	if (a.r < b.l)
  43. 		return 0;
  44. 	if (a.l > b.r)
  45. 		return 0;
  46. 	return 1;
  47. }
  48. int main()
  49. {
  50.     freopen("two.in", "r", stdin);
  51.     freopen("two.out", "w", stdout);
  52. 	cin >> n;
  53. 	for (int i = 1; i <= n; i++)
  54. 	{
  55. 		a[i].id = i;
  56. 		cin >> a[i].ls >> a[i].rs >> a[i].k;
  57. 		if (a[i].ls != 0)
  58. 		{
  59. 			e[i].push_back(a[i].ls);
  60. 			e[a[i].ls].push_back(i);
  61. 			fa[a[i].ls] = i;
  62. 		}
  63. 		if (a[i].rs != 0)
  64. 		{
  65. 			e[i].push_back(a[i].rs);
  66. 			e[a[i].rs].push_back(i);
  67. 			fa[a[i].rs] = i;
  68. 		}
  69. 	}
  70. 	a[0].sc = (sec){-2000000000, -2000000000};
  71. 	find_lr(1);
  72. 	int q;
  73. 	cin >> q;
  74. 	for (int i = 1; i <= n; i++)
  75. 	if (n <= 2000 && q <= 2000)
  76. 	{
  77. 		while (q--)
  78. 		{
  79. 			int L, R;
  80. 			cin >> L >> R;
  81. 			sec Wen = (sec){L, R};
  82. 			int ans = 0;
  83. 			for (int i = 1; i <= n; i++)
  84. 			{
  85. 				if (check(a[i].sc, Wen))
  86. 				{
  87. 					ans++;
  88. 					if (check(a[a[i].ls].sc, Wen) == 0)
  89. 						ans++;
  90. 					if (check(a[a[i].rs].sc, Wen) == 0)
  91. 						ans++;
  92. 				}
  93. 			}
  94. 			cout << ans << endl;
  95. 		}
  96. 		return 0;
  97. 	}
  98. 	return 0;
  99. }
Success #stdin #stdout 0.01s 8360KB
comments (?)
stdin
copy 
7
2 3 -1
0 0 -2
4 5 2
7 0 1
0 6 3
0 0 4
0 0 0
8
2 4
-2 -2
-1 -1
0 0
1 1
2 2
3 3
4 4
stdout
copy 
Standard output is empty
https://ideone.com/OyNOWs
language:
C++14 (gcc 8.3)
created:
5 hours 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!