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
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