fork(15) download
copy 
  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 LL maxval = MOD;
  17. const int maxn = 300005;
  18. vector<int> owner[maxn];
  19. LL reqd[maxn];
  20. int ql[maxn],qr[maxn];
  21. LL qa[maxn];
  22. int lo[maxn], hi[maxn];
  23. vector<int> tocheck[maxn];
  24.  
  25. long long tree[maxn];
  26. int n,m;
  27. int k;
  28. long long maxi=0;
  29. void update(int x, long long val){
  30. 	while(x<=m){
  31. 		tree[x]+=val;
  32. 		//[x]=min(tree[x],maxi);
  33. 		x+=(x&-x);
  34.  
  35. 	}
  36. }
  37. long long read(int x){
  38. 	long long s=0;
  39. 	while(x>0){
  40. 		s+=tree[x];
  41. 		//s=min(tree[x],maxi);
  42. 		x-=(x&-x);
  43. 	}
  44. 	return s;
  45. }
  46.  
  47. void apply(int x){
  48. 	if(ql[x]<=qr[x])
  49. 		update(ql[x],qa[x]),update(qr[x]+1,-qa[x]);
  50. 	else{
  51. 		update(1,qa[x]);
  52. 		update(qr[x]+1,-qa[x]);
  53. 		update(ql[x],qa[x]);
  54. 	}
  55. }
  56.  
  57. int main()
  58. {
  59. 	cin(n);
  60. 	cin(m);
  61. 	for(int i = 1; i <= m; i++)
  62. 	{
  63. 		int x;
  64. 		cin(x);
  65. 		owner[x].pb(i);
  66. 	}
  67. 	for(int i = 1; i <= n; i++)
  68. 		scanf("%lld",&reqd[i]);
  69. 	cin(k);
  70. 	for(int i = 1; i <= k; i++)
  71. 	{
  72. 		cin(ql[i]);
  73. 		cin(qr[i]);
  74. 		scanf("%lld",&qa[i]);
  75. 	}
  76. 	for(int i = 1; i <= n; i++)
  77. 	{
  78. 		lo[i] = 1;
  79. 		hi[i] = k + 1;
  80. 	}
  81. 	bool changed = true;
  82. 	while(changed)
  83. 	{
  84. 		changed = false;
  85.  
  86. 		// clean up mess.
  87. 		for(int a = 0; a <= m; a++)
  88. 			tree[a] = 0;
  89. 		for(int i = 1; i <= n; i++)
  90. 			if(lo[i] != hi[i])
  91. 				tocheck[ (lo[i] + hi[i]) >> 1 ].pb(i);
  92. 		// end of cleaning up
  93.  
  94. 		for(int q = 1; q <= k; q++)
  95. 		{
  96. 			apply(q);
  97.  
  98. 			while(sz(tocheck[q]))
  99. 			{
  100. 				changed = true;
  101. 				int id = tocheck[q].back();
  102. 				tocheck[q].pop_back();
  103.  
  104. 				LL sum = 0;
  105. 				for(auto sectors: owner[id])
  106. 				{
  107. 					sum += read(sectors);
  108. 					if(sum >= reqd[id]) break;
  109. 				}
  110. 				if(sum >= reqd[id])
  111. 					hi[id] = q;
  112. 				else
  113. 					lo[id] = q + 1;
  114. 			}
  115. 		}
  116. 	}
  117. 	for(int i = 1; i <= n; i++)
  118. 	{
  119. 		assert(lo[i] == hi[i]);		
  120. 		if(lo[i] <= k)
  121. 			printf("%d\n",lo[i]);
  122. 		else
  123. 			printf("NIE\n");
  124. 	}
  125. 	return 0;
  126. }
Success #stdin #stdout 0s 22208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tTO9bD
problem METEORS, based on SPOJ submission 17099806 (C++14), 2016-06-13 07:15:00
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!