fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n, m, k;
  4. int a[300005], ans[300005];
  5. long long bit[300005];
  6. vector <int> idx[300005];
  7.  
  8. struct ZATA {
  9.     int l, r, val;
  10. } ques[3000005];
  11.  
  12. vector <ZATA> vt[300005];
  13.  
  14. void upd(int pos, int val) {
  15.     while (pos <= m) {
  16.         bit[pos] += val;
  17.         pos += (pos & (-pos));
  18.     }
  19. }
  20.  
  21. void update(int l, int r, int val) {
  22.     upd(l, val);
  23.     upd(r + 1, -val);
  24. }
  25.  
  26. long long get(int pos) {
  27.     long long res = 0;
  28.     while (pos) {
  29.         res += bit[pos];
  30.         pos -= (pos & (-pos));
  31.     }
  32.     return res;
  33. }
  34.  
  35. main() {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(0); cout.tie(0);
  38.     freopen("TEST.inp", "r", stdin);
  39.     freopen("TEST.out", "w", stdout);
  40.     cin >> n >> m;
  41.     for (int i = 1; i <= m; i++) {
  42.         int a;
  43.         cin >> a;
  44.         idx[a].push_back(i);
  45.     }
  46.     for (int i = 1; i <= n; i++) cin >> a[i];
  47.     cin >> k;
  48.     for (int i = 1; i <= k; i++) cin >> ques[i].l >> ques[i].r >> ques[i].val;
  49.  
  50.     int dem = 0;
  51.     int mid = (k + 1) / 2;
  52.     for (int i = 1; i <= n; i++)
  53.         vt[mid].push_back({0, k + 1, i});
  54.     while (dem < n) {
  55.         memset(bit, 0, sizeof(bit));
  56.         for (int i = 1; i <= k; i++) {
  57.             auto [l, r, val] = ques[i];
  58.             if (l <= r) update(l, r, val);
  59.             else {
  60.                 update(1, r, val);
  61.                 update(l, m, val);
  62.             }
  63.             for (int j = 0; j < vt[i].size(); j++) {
  64.                 ZATA res = vt[i][j];
  65.                 long long sum = 0;
  66.                 for (auto pos : idx[res.val]) {
  67.                     sum += get(pos);
  68.                     if (sum >= a[res.val]) break;
  69.                 }
  70.                 if (sum >= a[res.val]) res.r = i;
  71.                 else res.l = i;
  72.                 mid = (res.l + res.r) / 2;
  73.                 if (res.l == res.r - 1) {
  74.                     ans[res.val] = res.r;
  75.                     dem++;
  76.                 } else vt[mid].push_back(res);
  77.             }
  78.             vt[i].clear();
  79.         }
  80.     }
  81.  
  82.     for (int i = 1; i <= n; i++)
  83.         if (ans[i] == k + 1 || ans[i] == 0) cout << "NIE" << '\n';
  84.         else cout << ans[i] << '\n';
  85.  
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0.01s 20696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fQ2Wfn
language:
C++14 (gcc 8.3)
created:
3 days 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!