fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ull unsigned long long
  5. #define pb push_back
  6.  
  7. const int N = 300005;
  8. const int M = 90;
  9. ull cnt[N], tree[N*M];
  10. int L[N*M], R[N*M], ind[N];
  11. vector<int> v[N];
  12. int node_cnt = 0;
  13.  
  14. int build(int l, int r)
  15. {
  16. 	node_cnt++;
  17. 	int node = node_cnt;
  18. 	tree[node] = 0;
  19.  
  20. 	if(l == r)
  21. 		return node;
  22. 	int mid = (l+r)>>1;
  23. 	L[node] = build(l, mid);
  24. 	R[node] = build(mid+1, r);
  25.  
  26. 	return node;
  27. }
  28.  
  29. void LazyPropagate(int node)
  30. {
  31. 	node_cnt++;
  32. 	int left = node_cnt;
  33. 	node_cnt++;
  34. 	int right = node_cnt;
  35.  
  36. 	L[left] = L[L[node]];
  37. 	R[left] = R[L[node]];
  38.  
  39. 	L[right] = L[R[node]];
  40. 	R[right] = R[R[node]];
  41.  
  42. 	tree[left] = tree[node] + tree[L[node]];
  43. 	tree[right] = tree[node] + tree[R[node]];
  44.  
  45. 	L[node] = left;
  46. 	R[node] = right;
  47. 	tree[node] = 0;
  48.  
  49. 	return;
  50. }
  51.  
  52. int update(int pnode, int l, int r, int a, int b, ull val)
  53. {
  54. 	node_cnt++;
  55. 	int node = node_cnt;
  56.  
  57. 	if(l == a && r == b)
  58. 	{
  59. 		tree[node] = tree[pnode] + val;
  60. 		L[node] = L[pnode];
  61. 		R[node] = R[pnode];
  62. 		return node;
  63. 	}
  64.  
  65. 	if(tree[pnode])
  66. 		LazyPropagate(pnode);
  67.  
  68. 	int mid = (l+r)>>1;
  69. 	L[node] = L[pnode];
  70. 	R[node] = R[pnode];
  71.  
  72. 	if(b<=mid)
  73. 		L[node] = update(L[pnode], l, mid, a, b, val);
  74. 	else if(a>mid)
  75. 		R[node] = update(R[pnode], mid+1, r, a, b, val);
  76. 	else
  77. 	{
  78. 		L[node] = update(L[pnode], l, mid, a, mid, val);
  79. 		R[node] = update(R[pnode], mid+1, r, mid+1, b, val);
  80. 	}
  81. 	return node;
  82. }
  83.  
  84. ull query(int node, int l, int r, int idx)
  85. {
  86. 	if(l == r)
  87. 		return tree[node];
  88. 	if(tree[node])
  89. 		LazyPropagate(node);
  90.  
  91. 	int mid = (l+r)>>1;
  92. 	if(idx<=mid)
  93. 		return query(L[node], l, mid, idx);
  94. 	return query(R[node], mid+1, r, idx);
  95. }
  96.  
  97. int main()
  98. {
  99. 	int n, m, k, l, r, q, mid, ow;
  100. 	ull a;
  101. 	scanf("%d %d", &n, &m);
  102. 	for(int i = 1; i<=m; i++)
  103. 	{
  104. 		scanf("%d", &ow);
  105. 		v[ow].pb(i);
  106. 	}
  107. 	for(int i = 1; i<=n; i++)
  108. 		scanf("%llu", &cnt[i]);
  109.  
  110. 	ind[0] = build(1, m);
  111.  
  112. 	scanf("%d", &q);
  113. 	for(int i = 1; i<=q; i++)
  114. 	{
  115. 		scanf("%d %d %llu", &l, &r, &a);
  116. 		if(l > r)
  117. 		{
  118. 			ind[i] = update(ind[i-1], 1, m, l, m, a);
  119. 			ind[i] = update(ind[i], 1, m, 1, r, a);
  120. 		}
  121. 		else
  122. 			ind[i] = update(ind[i-1], 1, m, l, r, a);
  123. 	}
  124.  
  125. 	ull total;
  126. 	for(int i = 1; i<=n; i++)
  127. 	{
  128. 		l = 1;
  129. 		r = q + 1;
  130. 		while(l<r)
  131. 		{
  132. 			mid = (l+r)>>1;
  133.  
  134. 			total = 0;
  135. 			for(int j = 0; j<v[i].size(); j++)
  136. 				total += query(ind[mid], 1, m, v[i][j]);
  137.  
  138. 			if(total < cnt[i])
  139. 				l = mid + 1;
  140. 			else
  141. 				r = mid;
  142. 		}
  143. 		if(l == (q + 1))
  144. 			printf("NIE\n");
  145. 		else
  146. 			printf("%d\n", l);
  147. 	}
  148.  
  149. 	return 0;
  150. }
Success #stdin #stdout 0s 448512KB
comments (?)
stdin
copy 
3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2
stdout
copy 
3
NIE
1
https://ideone.com/x7dwqq
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

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!