fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define f first
  5. #define s second
  6. #define mp make_pair
  7. #define sz(a) int((a).size())
  8. #ifdef _WIN32
  9. #  define I64 "%I64d"
  10. #else
  11. #  define I64 "%lld"
  12. #endif
  13. #define fname "."
  14. #define pi pair < int, int >
  15. #define pp pop_back
  16.  
  17. typedef long long ll;
  18. typedef long double ld;
  19. typedef unsigned long long ull;
  20.  
  21. const int MAX_N = (int)5e5 + 123;
  22. const double eps = 1e-6;
  23. const int inf = (int)1e9 + 123;
  24.  
  25. using namespace std;
  26.  
  27. int n, m, q;
  28. vector < int > g[MAX_N];
  29. vector < int > own[MAX_N];
  30. ll need[MAX_N];
  31.  
  32. struct tree {
  33. 	ll add;
  34. 	int l, r;
  35. 	tree() : add(0), l(-1), r(-1) {}
  36. };
  37.  
  38. vector < tree > t, t2;
  39.  
  40. int update(int l, int r, ll x, int v, int tl = 1, int tr = n) {
  41. 	if (tl > r || l > tr)
  42. 		return v;
  43. 	int now = sz(t);
  44. 	t.pb(tree());
  45. 	if (v != -1)
  46. 		t[now] = t[v];
  47. 	if (tl >= l && tr <= r) {
  48. 		t[now].add += x;
  49. 		return now;
  50. 	}
  51. 	int tm = (tl + tr) / 2;
  52. 	int hey = update(l, r, x, (v == -1 ? -1 : t[v].l), tl, tm);
  53. 	t[now].l = hey;
  54. 	hey = update(l, r, x, (v == -1 ? -1 : t[v].r), tm + 1, tr);
  55. 	t[now].r = hey;
  56. 	return now;
  57. }
  58.  
  59. ll get(int x, int v, int tl = 1, int tr = n) {
  60. 	if (v == -1)
  61. 		return 0;
  62. 	if (tl == tr)
  63. 		return t[v].add;
  64. 	int tm = (tl + tr) / 2;
  65. 	if (x <= tm)
  66. 		return t[v].add + get(x, t[v].l, tl, tm);
  67. 	return t[v].add + get(x, t[v].r, tm + 1, tr);
  68. }
  69.  
  70. int update2(int l, int r, ll x, int v, int tl = 1, int tr = n) {
  71. 	if (tl > r || l > tr)
  72. 		return v;
  73. 	int now = sz(t2);
  74. 	t2.pb(tree());
  75. 	if (v != -1)
  76. 		t2[now] = t2[v];
  77. 	if (tl >= l && tr <= r) {
  78. 		t2[now].add += x;
  79. 		return now;
  80. 	}
  81.  
  82. 	int tm = (tl + tr) / 2;
  83.  
  84. // -----
  85. 	int hey = update2(l, r, x, (v == -1 ? -1 : t2[v].l), tl, tm);
  86. 	t2[now].l = hey;
  87. 	hey = update2(l, r, x, (v == -1 ? -1 : t2[v].r), tm + 1, tr);
  88. 	t2[now].r = hey;
  89. // -----
  90.  
  91.  
  92. /*	t2[now].l = update2(l, r, x, (v == -1 ? -1 : t2[v].l), tl, tm);
  93. 	t2[now].r = update2(l, r, x, (v == -1 ? -1 : t2[v].r), tm + 1, tr);*/
  94.  
  95. 	return now;
  96. }
  97.  
  98. ll get2(int x, int v, int tl = 1, int tr = n) {
  99. 	if (v == -1)
  100. 		return 0;
  101. 	if (tl == tr)
  102. 		return t2[v].add;
  103. 	int tm = (tl + tr) / 2;
  104. 	if (x <= tm)
  105. 		return t2[v].add + get2(x, t2[v].l, tl, tm);
  106. 	return t2[v].add + get2(x, t2[v].r, tm + 1, tr);
  107. }
  108.  
  109. pi root[MAX_N];
  110. int L[MAX_N], R[MAX_N], timer;
  111. int lvl[MAX_N];
  112.  
  113. void dfs(int v, int pr = 0) {
  114. 	lvl[v] = lvl[pr] + 1;
  115. 	L[v] = ++timer;
  116. 	for (auto to : g[v])
  117. 		dfs(to, v);
  118. 	R[v] = timer;
  119. }
  120.  
  121. bool check(int id, int x) {
  122. 	ll res = 0;
  123. 	for (auto i : own[x])
  124. 		res += 1ll * lvl[i] * get(L[i], root[id].f) + get2(L[i], root[id].s);
  125. 	return (res >= need[x]);
  126. }
  127.  
  128. int Find(int x) {
  129. 	int l = 1, r = q, mid = -1, ans = -1;
  130. 	while(l <= r) {
  131. 		mid = (l + r) / 2;
  132. 		if (check(mid, x))
  133. 			ans = mid, r = mid - 1;
  134. 		else
  135. 			l = mid + 1;
  136. 	}
  137. 	return ans;
  138. }
  139.  
  140. int main() {
  141. 	scanf("%d%d", &n, &m);
  142. 	for (int i = 2, x; i <= n; i++) {
  143. 		scanf("%d", &x);
  144. 		g[x].pb(i);
  145. 	}
  146. 	for (int i = 1, x; i <= n; i++) {
  147. 		scanf("%d", &x);
  148. 		own[x].pb(i);
  149. 	}
  150. 	for (int i = 1; i <= m; i++)
  151. 		scanf(I64, &need[i]);
  152. 	dfs(1);
  153. 	scanf("%d", &q);
  154. 	for (int i = 1, v, x, d; i <= q; i++) {
  155. 	  scanf("%d%d%d", &v, &x, &d);
  156. 		int last = (i == 1 ? -1 : root[i - 1].f);
  157. 		root[i].f = update(L[v], R[v], d, last);
  158.  
  159. 		last = (i == 1 ? -1 : root[i - 1].s);
  160. 		ll now = 0ll - 1ll * lvl[v] * d + x;
  161. 		root[i].s = update2(L[v], R[v], now, last);
  162. 	}
  163. 	for (int i = 1; i <= m; i++) {
  164. 		int ans = Find(i);
  165. 		if (ans == -1)
  166. 			printf("rekt\n");
  167. 		else
  168. 			printf("%d\n", ans);
  169. 	}
  170. 	return 0;
  171. }
  172.  
Success #stdin #stdout 0.02s 28864KB
comments (?)
stdin
copy 
3 3
1 2
1 2 3
10 15 20
5
1 2 3
2 2 3
3 5 10
1 4 0
1 3 3
stdout
copy 
rekt
5
4
https://ideone.com/QxhGT6
language:
C++14 (gcc 8.3)
created:
8 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!