fork(10) 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 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
stdin
Standard input is empty
stdout
Standard output is empty