fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ull unsigned long long
  5. #define pb push_back
  6.  
  7. const int N = 300005;
  8. const int M = 200;
  9. ull cnt[N], tree[N*M];
  10. int L[N*M], R[N*M], ind[N];
  11. vector<int> v[N];
  12. int node_cnt = 0;
  13.  
  14. int build(int l, int r)
  15. {
  16. node_cnt++;
  17. int node = node_cnt;
  18. tree[node] = 0;
  19.  
  20. if(l == r)
  21. return node;
  22. int mid = (l+r)>>1;
  23. L[node] = build(l, mid);
  24. R[node] = build(mid+1, r);
  25.  
  26. return node;
  27. }
  28.  
  29. void LazyPropagate(int node)
  30. {
  31. node_cnt++;
  32. int left = node_cnt;
  33. node_cnt++;
  34. int right = node_cnt;
  35.  
  36. L[left] = L[L[node]];
  37. R[left] = R[L[node]];
  38.  
  39. L[right] = L[R[node]];
  40. R[right] = R[R[node]];
  41.  
  42. tree[left] = tree[node] + tree[L[node]];
  43. tree[right] = tree[node] + tree[R[node]];
  44.  
  45. L[node] = left;
  46. R[node] = right;
  47. tree[node] = 0;
  48.  
  49. return;
  50. }
  51.  
  52. int update(int pnode, int l, int r, int a, int b, ull val)
  53. {
  54. node_cnt++;
  55. int node = node_cnt;
  56.  
  57. if(l == a && r == b)
  58. {
  59. tree[node] = tree[pnode] + val;
  60. L[node] = L[pnode];
  61. R[node] = R[pnode];
  62. return node;
  63. }
  64.  
  65. if(tree[pnode])
  66. LazyPropagate(pnode);
  67.  
  68. int mid = (l+r)>>1;
  69. L[node] = L[pnode];
  70. R[node] = R[pnode];
  71.  
  72. if(b<=mid)
  73. L[node] = update(L[pnode], l, mid, a, b, val);
  74. else if(a>mid)
  75. R[node] = update(R[pnode], mid+1, r, a, b, val);
  76. else
  77. {
  78. L[node] = update(L[pnode], l, mid, a, mid, val);
  79. R[node] = update(R[pnode], mid+1, r, mid+1, b, val);
  80. }
  81. return node;
  82. }
  83.  
  84. ull query(int node, int l, int r, int idx)
  85. {
  86. if(l == r)
  87. return tree[node];
  88. if(tree[node])
  89. LazyPropagate(node);
  90.  
  91. int mid = (l+r)>>1;
  92. if(idx<=mid)
  93. return query(L[node], l, mid, idx);
  94. return query(R[node], mid+1, r, idx);
  95. }
  96.  
  97. int main()
  98. {
  99. int n, m, k, l, r, q, mid, ow;
  100. ull a;
  101. scanf("%d %d", &n, &m);
  102. for(int i = 1; i<=m; i++)
  103. {
  104. scanf("%d", &ow);
  105. v[ow].pb(i);
  106. }
  107. for(int i = 1; i<=n; i++)
  108. scanf("%llu", &cnt[i]);
  109.  
  110. ind[0] = build(1, m);
  111.  
  112. scanf("%d", &q);
  113. for(int i = 1; i<=q; i++)
  114. {
  115. scanf("%d %d %llu", &l, &r, &a);
  116. if(l > r)
  117. {
  118. ind[i] = update(ind[i-1], 1, m, l, m, a);
  119. ind[i] = update(ind[i], 1, m, 1, r, a);
  120. }
  121. else
  122. ind[i] = update(ind[i-1], 1, m, l, r, a);
  123. }
  124.  
  125. ull total;
  126. for(int i = 1; i<=n; i++)
  127. {
  128. l = 1;
  129. r = q + 1;
  130. while(l<r)
  131. {
  132. mid = (l+r)>>1;
  133.  
  134. total = 0;
  135. for(int j = 0; j<v[i].size(); j++)
  136. total += query(ind[mid], 1, m, v[i][j]);
  137.  
  138. if(total < cnt[i])
  139. l = mid + 1;
  140. else
  141. r = mid;
  142. }
  143. if(l == (q + 1))
  144. printf("NIE\n");
  145. else
  146. printf("%d\n", l);
  147. }
  148.  
  149. return 0;
  150. }
Success #stdin #stdout 0.01s 10104KB
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