fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Fenwick {
  5.     int n;
  6.     vector<long long> bit;
  7.     Fenwick(int n) : n(n), bit(n + 1, 0) {}
  8.  
  9.     void add(int i, long long v) {
  10.         for (; i <= n; i += i & -i)
  11.             bit[i] += v;
  12.     }
  13.  
  14.     void range_add(int l, int r, long long v) {
  15.         add(l, v);
  16.         add(r + 1, -v);
  17.     }
  18.  
  19.     long long query(int i) {
  20.         long long s = 0;
  21.         for (; i > 0; i -= i & -i)
  22.             s += bit[i];
  23.         return s;
  24.     }
  25. };
  26.  
  27. int main() {
  28.     ios::sync_with_stdio(false);
  29.     cin.tie(nullptr);
  30.  
  31.     int n, m;
  32.     cin >> n >> m;
  33.  
  34.     vector<int> owner(m + 1);
  35.     for (int i = 1; i <= m; i++)
  36.         cin >> owner[i];
  37.  
  38.     vector<long long> need(n + 1);
  39.     for (int i = 1; i <= n; i++)
  40.         cin >> need[i];
  41.  
  42.     vector<vector<int>> sectors(n + 1);
  43.     for (int i = 1; i <= m; i++)
  44.         sectors[owner[i]].push_back(i);
  45.  
  46.     int q;
  47.     cin >> q;
  48.     vector<int> L(q + 1), R(q + 1);
  49.     vector<long long> Z(q + 1);
  50.  
  51.     for (int i = 1; i <= q; i++)
  52.         cin >> L[i] >> R[i] >> Z[i];
  53.  
  54.     vector<int> lo(n + 1, 1), hi(n + 1, q + 1), ans(n + 1, -1);
  55.     bool changed = true;
  56.  
  57.     while (changed) {
  58.         changed = false;
  59.         vector<vector<int>> bucket(q + 1);
  60.  
  61.         for (int i = 1; i <= n; i++) {
  62.             if (lo[i] < hi[i]) {
  63.                 int mid = (lo[i] + hi[i]) / 2;
  64.                 bucket[mid].push_back(i);
  65.                 changed = true;
  66.             }
  67.         }
  68.  
  69.         Fenwick fw(m);
  70.  
  71.         for (int i = 1; i <= q; i++) {
  72.             if (L[i] <= R[i]) {
  73.                 fw.range_add(L[i], R[i], Z[i]);
  74.             } else {
  75.                 fw.range_add(L[i], m, Z[i]);
  76.                 fw.range_add(1, R[i], Z[i]);
  77.             }
  78.  
  79.             for (int c : bucket[i]) {
  80.                 long long sum = 0;
  81.                 for (int s : sectors[c]) {
  82.                     sum += fw.query(s);
  83.                     if (sum >= need[c]) break;
  84.                 }
  85.                 if (sum >= need[c]) hi[c] = i;
  86.                 else lo[c] = i + 1;
  87.             }
  88.         }
  89.     }
  90.  
  91.     for (int i = 1; i <= n; i++) {
  92.         if (lo[i] <= q) cout << lo[i] << "\n";
  93.         else cout << "NIE\n";
  94.     }
  95.  
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2
stdout
copy 
3
NIE
1
https://ideone.com/KmDxiT
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!