fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ff first
  6. #define ss second
  7. #define pb push_back
  8. #define mp make_pair
  9. #define all(x) x.begin(),x.end()
  10. #define sz(x) ((int)x.size())
  11. const int MOD = 1e9+7;
  12.  
  13. typedef long long ll;
  14. typedef pair<int,int> pii;
  15.  
  16. int m;
  17. const int MAXN = 3e5+5;
  18. ll BIT[MAXN];
  19. vector<int> mid[MAXN],mem[MAXN];
  20. int reqd[MAXN];
  21. int x[MAXN],y[MAXN],z[MAXN];
  22. int ans[MAXN];
  23. int l[MAXN],r[MAXN];
  24. void update(int idx, int val) {
  25. 	while(idx<=m) {
  26. 		BIT[idx]+=1LL*val;
  27. 		idx+=(idx&-idx);
  28. 	}
  29. }
  30. ll query(int idx) {
  31. 	ll ret=0;
  32. 	while(idx) {
  33. 		ret+=BIT[idx];
  34. 		idx-=(idx&-idx);
  35. 	}
  36. 	return ret;
  37. }
  38. int main() {
  39. 	// freopen("TASK.in","r",stdin);	
  40. 	// freopen("TASK.out","w",stdout);
  41. 	int n;
  42. 	cin>>n>>m;
  43. 	for(int i=1;i<=m;i++) {
  44. 		int x;
  45. 		scanf("%d",&x);
  46. 		mem[x].pb(i);
  47. 	}
  48. 	for(int i=1;i<=n;i++)
  49. 		scanf("%d",&reqd[i]);
  50. 	int q;
  51. 	cin>>q;
  52. 	for(int i=1;i<=q;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]);
  53. 	for(int i=1;i<=n;i++) l[i]=1,r[i]=q,ans[i]=-1;
  54. 	bool changed=true;
  55. 	while(changed) {
  56. 		changed=false;
  57. 		for(int i=0;i<=q;i++) mid[i].clear();
  58. 		for(int i=0;i<=m;i++) BIT[i]=0;
  59. 		for(int i=1;i<=n;i++) {
  60. 			if(l[i]<=r[i]) {
  61. 				mid[l[i]+(r[i]-l[i]+1)/2].pb(i);
  62. 			}
  63. 		}
  64. 		for(int i=1;i<=q;i++) {
  65. 			if(x[i]<=y[i]) {
  66. 				update(x[i],z[i]);
  67. 				update(y[i]+1,-z[i]);
  68. 			}
  69. 			else {
  70. 				update(x[i],z[i]);
  71. 				update(1,z[i]);
  72. 				update(y[i]+1,-z[i]);
  73. 			}
  74. 			for(auto it:mid[i]) {
  75. 				changed=true;
  76. 				ll qu=0;
  77. 				for(auto j:mem[it]) qu+=query(j);
  78. 				if(qu>=reqd[it]) {
  79. 					ans[it]=i;
  80. 					r[it]=i-1;
  81. 				}
  82. 				else l[it]=i+1;
  83. 			}
  84. 		}
  85. 	}
  86. 	for(int i=1;i<=n;i++) if(ans[i]==-1) printf("NIE\n");else printf("%d\n",ans[i]);
  87. 	return 0;
  88. }
Success #stdin #stdout 0s 21000KB
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/zv9HDQ
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!