fork download
copy 
  1. // Author: __BruteForce__
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long int64;
  7.  
  8. #define MAX_N 300005
  9.  
  10. int n, m, k;
  11. vector<int> state[MAX_N];
  12. int64 reqd[MAX_N];
  13. int lo[MAX_N], hi[MAX_N], ql[MAX_N], qr[MAX_N];
  14. int64 qa[MAX_N];
  15. int64 bit[MAX_N];
  16. stack<int> to_check[MAX_N];
  17.  
  18. void init() {
  19.     cin >> n >> m;
  20.     for (int i = 1; i <= m; i++) {
  21.         int o;
  22.         cin >> o;
  23.         state[o].push_back(i);
  24.     }
  25.     for (int i = 1; i <= n; i++) cin >> reqd[i];
  26.     cin >> k;
  27.     for (int i = 1; i <= k; i++) cin >> ql[i] >> qr[i] >> qa[i];
  28.     for (int i = 1; i <= n; i++) lo[i] = 1, hi[i] = k + 1;
  29. }
  30.  
  31. void update_bit(int p, int64 v) {
  32.     for (; p <= m; p += p & -p) bit[p] += v;
  33. }
  34.  
  35. int64 get_bit(int p) {
  36.     int64 sum = 0;
  37.     for (; p; p -= p & -p) sum += bit[p];
  38.     return sum;
  39. }
  40.  
  41. void update(int idx) {
  42.     update_bit(ql[idx], qa[idx]);
  43.     update_bit(qr[idx] + 1, -qa[idx]);
  44.     if (ql[idx] > qr[idx]) update_bit(1, qa[idx]);
  45. }
  46.  
  47. void solve() {
  48.     bool changed = true;
  49.     // Parallel Binary Search
  50.     while (changed) {
  51.         changed = false;
  52.  
  53.         // Reset
  54.         memset(bit, 0, sizeof(bit));
  55.         for (int i = 1; i <= n; i++)
  56.             if (lo[i] != hi[i]) to_check[(lo[i] + hi[i]) >> 1].push(i);
  57.  
  58.         // Update
  59.         for (int i = 1; i <= k; i++) {
  60.             update(i);
  61.             while (to_check[i].size()) {
  62.                 changed = true;
  63.                 int idx = to_check[i].top();
  64.                 to_check[i].pop();
  65.  
  66.                 int64 sum = 0;
  67.                 for (auto sector : state[idx]) {
  68.                     sum += get_bit(sector);
  69.                     if (sum >= reqd[idx]) break;
  70.                 }
  71.                 if (sum >= reqd[idx])
  72.                     hi[idx] = i;
  73.                 else
  74.                     lo[idx] = i + 1;
  75.             }
  76.         }
  77.     }
  78.  
  79.     for (int i = 1; i <= n; i++)
  80.         if (lo[i] <= k)
  81.             cout << lo[i] << "\n";
  82.         else
  83.             cout << "NIE\n";
  84. }
  85.  
  86. int main() {
  87.     cin.tie(0)->sync_with_stdio(false);
  88.  
  89.     init();
  90.     solve();
  91. }
Success #stdin #stdout 0.11s 214964KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IsUYH6
language:
C++14 (gcc 8.3)
created:
1 year 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!