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 output = 0;
  49. sec Wen;
  50. void run(int x)
  51. {
  52. 	output++;
  53. 	if (x == 0)
  54. 		return ;
  55. 	if (check(a[x].sc, Wen) == 0)
  56. 		return ;
  57. 	run(a[x].ls);
  58. 	run(a[x].rs);
  59. }
  60. map <pair<int, int>, int> mem;
  61. int mapp[2010];
  62. int main()
  63. {
  64.     freopen("two.in", "r", stdin);
  65.     freopen("two.out", "w", stdout);
  66. 	cin >> n;
  67. 	for (int i = 1; i <= n; i++)
  68. 	{
  69. 		a[i].id = i;
  70. 		cin >> a[i].ls >> a[i].rs >> a[i].k;
  71. 		if (a[i].ls != 0)
  72. 		{
  73. 			e[i].push_back(a[i].ls);
  74. 			e[a[i].ls].push_back(i);
  75. 			fa[a[i].ls] = i;
  76. 		}
  77. 		if (a[i].rs != 0)
  78. 		{
  79. 			e[i].push_back(a[i].rs);
  80. 			e[a[i].rs].push_back(i);
  81. 			fa[a[i].rs] = i;
  82. 		}
  83. 		mapp[i] = a[i].k;
  84. 	}
  85. 	sort (mapp + 1, mapp + n + 1);
  86. 	a[0].sc = (sec){-2000000000, -2000000000};
  87. 	find_lr(1);
  88. 	int q;
  89. 	cin >> q;
  90. 	if (n <= 2000 && q <= 2000)
  91. 	{
  92. 		while (q--)
  93. 		{
  94. 			int L, R;
  95. 			cin >> L >> R;
  96. 			Wen = (sec){L, R};
  97. 			output = 0;
  98. 			run(1);
  99. 			cout << output << endl;
  100. 		}
  101. 		return 0;
  102. 	}
  103. 	while (q--)
  104. 	{
  105. 		int L, R;
  106. 		cin >> L >> R;
  107. 		Wen = (sec){L, R};
  108. 		pair <int, int> memchk;
  109. 		memchk.first = lower_bound(mapp + 1, mapp + n + 1, L) - mapp;
  110. 		memchk.second = upper_bound(mapp + 1, mapp + n + 1, R) - mapp - 1;
  111. 		if (mem.find(memchk) != mem.end())
  112. 		{
  113. 			cout << mem[memchk] << endl;
  114. 		}
  115. 		else
  116. 		{
  117. 			output = 0;
  118. 			run(1);
  119. 			cout << output << endl;
  120. 			mem[memchk] = output;
  121. 		}
  122. 		// cout << memchk.first << " " << memchk.second << endl;
  123. 	}
  124. 	return 0;
  125. }
Success #stdin #stdout 0.01s 8724KB
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/QHsx92
language:
C++14 (gcc 8.3)
created:
5 days 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!