fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long LL;
  5.  
  6. #define PII       pair<int,int>
  7. #define all(c)    c.begin(),c.end()
  8. #define sz(c)     (int)c.size()
  9. #define clr(c)    c.clear()
  10. #define pb        push_back
  11. #define mp        make_pair
  12. #define cin(x)    scanf("%d",&x)
  13. #define MOD		1000000007
  14. #define EPS		1E-10
  15.  
  16. const int maxn = 300010;
  17.  
  18. vector<int> owns[maxn]; // who owns whom
  19. int owner[maxn]; // given array
  20. int reqd[maxn]; // required samples
  21.  
  22. vector<int> tocheck[maxn]; // the parallel binary search
  23. int L[maxn], R[maxn]; // left and right.
  24.  
  25. int ql[maxn],qr[maxn],qa[maxn];
  26.  
  27. // segtree
  28.  
  29. int segtree[1000000];
  30. int lazy[1000000];
  31.  
  32. void buildTree(int l,int r,int pos)
  33. {
  34. 	if(l == r)
  35. 	{
  36. 		segtree[pos] = 0;
  37. 		lazy[pos] = 0;
  38. 	}
  39. 	else
  40. 	{
  41. 		int mid = (l + r) >> 1;
  42. 		buildTree(l,mid,2*pos);
  43. 		buildTree(mid+1,r,2*pos+1);
  44. 		segtree[pos] = segtree[2*pos] + segtree[2*pos+1];
  45. 		lazy[pos] = 0;
  46. 	}
  47. }
  48.  
  49. void lazyu(int l,int r,int pos)
  50. {
  51. 	if(lazy[pos] == 0) return;
  52. 	segtree[pos] = (int)min(1000000000LL, segtree[pos] + (r - l + 1LL) * lazy[pos]);
  53. 	if(l != r)
  54. 	{
  55. 		lazy[2*pos] += lazy[pos];
  56. 		lazy[2*pos + 1] += lazy[pos];
  57.  
  58. 		lazy[2*pos] = min(lazy[2*pos],1000000000);
  59. 		lazy[2*pos+1] = min(lazy[2*pos+1],1000000000);
  60. 	}
  61. 	lazy[pos] = 0;
  62. }
  63.  
  64. void update(int lQ,int rQ,int val,int l,int r,int pos)
  65. {
  66. 	lazyu(l,r,pos);
  67. 	if(l > r or l > rQ or r < lQ or lQ > rQ) return ;
  68. 	if(l >= lQ && r <= rQ)
  69. 	{
  70. 		segtree[pos] = (int)min(1000000000LL, segtree[pos] + (r - l + 1LL) * val);
  71. 		if(l != r)
  72. 		{
  73. 			lazy[2 * pos] += val;
  74. 			lazy[2 * pos + 1] += val;
  75.  
  76. 			lazy[2*pos] = min(lazy[2*pos],1000000000);
  77. 			lazy[2*pos+1] = min(lazy[2*pos+1],1000000000);
  78. 		}
  79. 		return ;
  80. 	}
  81. 	int mid = (l + r) >> 1;
  82. 	update(lQ,rQ,val,l,mid,2*pos);
  83. 	update(lQ,rQ,val,mid+1,r,2*pos+1);
  84. 	segtree[pos] = segtree[2*pos] + segtree[2*pos+1];
  85. 	segtree[pos] = min(segtree[pos],1000000000);
  86. }
  87.  
  88. int query(int lQ,int rQ,int l,int r,int pos)
  89. {
  90. 	lazyu(l,r,pos);
  91. 	if(l > r or lQ > rQ or l > rQ or r < lQ) return 0;
  92. 	else if(l >= lQ && r <= rQ) return segtree[pos];
  93. 	int mid = (l + r) >> 1;
  94. 	int ret = query(lQ,rQ,l,mid,2*pos) + query(lQ,rQ,mid+1,r,2*pos+1);
  95. 	return (ret >= 1000000000) ? 1000000000 : ret;
  96. }
  97.  
  98. // end of segtree
  99.  
  100. int n,m,k;
  101.  
  102. void cleanup()
  103. {
  104. 	for(int i = 1; i <= k + 1; i++)
  105. 		clr(tocheck[i]);
  106. 	for(int i = 1; i <= n; i++)
  107. 		if(L[i] != R[i])
  108. 			tocheck[ (L[i] + R[i])/2 ].pb(i);
  109. }
  110.  
  111. int main()
  112. {
  113. 	cin(n);
  114. 	cin(m);
  115. 	for(int i = 1; i <= m; i++)
  116. 	{
  117. 		cin(owner[i]);
  118. 		owns[owner[i]].pb(i);
  119. 	}
  120. 	for(int i = 1; i <= n; i++)
  121. 		cin(reqd[i]);
  122. 	cin(k);
  123. 	for(int i = 1; i <= n; i++)
  124. 	{
  125. 		L[i] = 1;
  126. 		R[i] = k + 1;
  127. 	}
  128. 	for(int i = 1; i <= k; i++)
  129. 	{
  130. 		cin(ql[i]);
  131. 		cin(qr[i]);
  132. 		cin(qa[i]);
  133. 	}
  134. 	int changed = 1;
  135. 	while(changed)
  136. 	{
  137. 		changed = 0;
  138. 		cleanup();
  139. 		buildTree(1,m,1);
  140.  
  141. 		for(int q = 1; q <= k; q++)
  142. 		{
  143. 			// apply updates and then use tocheck
  144. 			if(ql[q] > qr[q])
  145. 			{
  146. 				update(ql[q],m,qa[q],1,m,1);
  147. 				update(1,qr[q],qa[q],1,m,1);
  148. 			}
  149. 			else
  150. 				update(ql[q],qr[q],qa[q],1,m,1);
  151.  
  152. 			for(auto id: tocheck[q])
  153. 			{
  154. 				changed = 1;
  155. 				int sum = 0;
  156. 				for(auto sector: owns[id])
  157. 				{
  158. 					sum += query(sector,sector,1,m,1);
  159. 					if(sum >= reqd[id]) break;
  160. 				}
  161. 				if(sum >= reqd[id])
  162. 					R[id] = q;
  163. 				else
  164. 					L[id] = q + 1;
  165. 			}
  166. 		}
  167. 	}
  168. 	for(int i = 1; i <= n; i++)
  169. 	{
  170. 		assert(L[i] == R[i]);
  171. 		if(L[i] > k)
  172. 			printf("NIE\n");
  173. 		else
  174. 			printf("%d\n",L[i]);
  175. 	}
  176. 	return 0;
  177. }
Success #stdin #stdout 0s 26464KB
comments (?)
stdin 
3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2
stdout 
3
NIE
1
https://ideone.com/7l4nSx
problem METEORS, based on SPOJ submission 17094237 (C++14), 2016-06-12 10:43:47
language:
C++14 (gcc 8.3)
created:
8 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!