#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; constexpr int MAXN = 1'000'007; constexpr int INF = 2'000'000'000; constexpr ll INFF = 1'000'000'000'000'000'000LL; constexpr ll MOD = 998'244'353; #define mkp make_pair #define F first #define S second #define pb emplace_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() struct BIT { int n; vector<ll> d; void init(int nn) { n = nn; d.resize(n + 1); } void add(int x, ll dd) { for (int i = x; i <= n; i += (i & (-i))) d[i] += dd; } int kth(int k) { int ret = 0; for (int i = 21; i >= 0; i--) { if (ret + (1 << i) <= n && k - d[(1 << i) + ret] > 0) k -= d[(1 << i) + ret], ret += (1 << i); } return ret + 1; } ll query(int x) { if (x <= 0) return 0LL; ll ret = 0; for (int i = x; i > 0; i -= (i & (-i))) ret += d[i]; return ret; } } bit; int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; // assert(n >= 1 && n <= 300000); // assert(m >= 1 && m <= 300000); vector<int> a(m + 1), o(n + 1); vector<vector<int>> reg(n + 1); for (int i = 1; i <= m; i++) { cin >> a[i], reg[a[i]].pb(i); // assert(a[i] >= 1 && a[i] <= n); } for (int i = 1; i <= n; i++) { cin >> o[i]; // assert(o[i] >= 1 && o[i] <= 1000000000); } int k; cin >> k; assert(k >= 1 && k <= 300000); vector<tuple<int, int, int>> op(k); for (auto &[l, r, x] : op) { cin >> l >> r >> x; // assert(l >= 1 && l <= m); // assert(r >= 1 && r <= m); // assert(x >= 1 && x <= 1000000000); } vector<int> ans(n + 1); bit.init(m); auto solve = [&](auto solve, int l, int r, vector<int> queries) -> void { if (l == r) { for (auto i : queries) ans[i] = l; return; } int mid = (l + r) >> 1; for (int i = l; i <= mid; i++) { auto [li, ri, x] = op[i]; if (li <= ri) { bit.add(li, x); bit.add(ri + 1, -x); } else { bit.add(li, x); bit.add(1, x); bit.add(ri + 1, -x); } } vector<int> q1, q2; for (auto i : queries) { ll sum = 0; for (int j : reg[i]) sum += bit.query(j); if (sum >= o[i]) q1.pb(i); else q2.pb(i); } solve(solve, mid + 1, r, q2); for (int i = l; i <= mid; i++) { auto [li, ri, x] = op[i]; if (li <= ri) { bit.add(li, -x); bit.add(ri + 1, x); } else { bit.add(li, -x); bit.add(1, -x); bit.add(ri + 1, x); } } solve(solve, l, mid, q1); }; vector<int> q(n); for (int i = 0; i < n; i++) q[i] = i + 1; solve(solve, 0, k, q); for (int i = 1; i <= n; i++) { if (ans[i] == k) cout << "NIE\n"; else cout << ans[i] + 1 << '\n'; } } /* - How to come up with solutions? (https://hackmd.io/-3cIVAFSQMC3iJTh9EpszA) - Play with some small examples. - Make observations (or random guesses) by intuition. - Try to find counterexamples of the "observations." - Find the characteristics of an optimal solution. - Try to solve simple cases. - Brute force and print out the results. - Pick a method (greedy, dp, d&c, ...) - But DO NOT force algos on problems! - IF YOU'RE STUCK, TRY SOMETHING ELSE! Make new observations! - Before writing the solution: - check TL/ML/correctness of samples/implementation details! - Pre-submit: - Did you make a typo when copying a template? - Test more cases if unsure. - Write a naive solution and check small cases. - Submit the correct file. - Debugging: - General Debugging: - Read the whole problem again. - Think over the algorithm again. - Go to the toilet. - Wrong Answer: - Any possible overflows? - > `__int128` ? - Try `-ftrapv` or `#pragma GCC optimize("trapv")` - Floating point errors? - > `long double` ? - turn off math optimizations - check for `==`, `>=`, `acos(1.000000001)`, etc. - Did you forget to sort or unique? - Generate large and worst "corner" cases. - Check your `m` / `n`, `i` / `j`, `x` / `y` and `<` / `>`. - Are everything initialized or reset properly? - Are you sure about the STL thing you are using? - Read cppreference. - Print everything and run it on pen and paper. - Time Limit Exceeded: - Calculate your time complexity again. - Does the program actually end? - Check for `while(q.size())` etc. - Test the largest cases locally. - Did you do unnecessary stuff? - e.g. pass vectors by value - e.g. `memset` for every test case - Is your constant factor reasonable? - Runtime Error: - Check memory usage. - Forget to clear or destroy stuff? - > `vector::shrink_to_fit()` - Stack overflow? - Bad pointer / array access? - Try `-fsanitize=address` - Division by zero? NaN's? */