Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <iostream>
- #include <vector>
- using namespace std;
- #define endl '\n'
- const int maxN = 3 << 17;
- const int maxK = 1 << 10;
- const int INF = (int)1e9;
- typedef long long ll;
- int o[maxN];
- ll add[maxN];
- ll need[maxN];
- int start[maxN];
- ll startNeed[maxN];
- int l[maxN];
- int r[maxN];
- ll a[maxN];
- vector<int> pos[maxN];
- int main() {
- ios_base::sync_with_stdio(0);
- for (int i = 0; i < maxN; i++) {
- start[i] = INF;
- }
- int n, m;
- cin >> n >> m;
- for (int i = 1; i <= m; i++) {
- cin >> o[i];
- pos[o[i]].push_back(i);
- }
- for (int i = 1; i <= n; i++) {
- cin >> need[i];
- }
- int q;
- cin >> q;
- for (int i = 1; i <= q; i++) { // O((m + n) * q / maxK)
- cin >> l[i] >> r[i] >> a[i];
- if (l[i] > r[i]) {
- add[1] += a[i];
- add[r[i] + 1] -= a[i];
- add[l[i]] += a[i];
- add[m + 1] -= a[i];
- } else {
- add[l[i]] += a[i];
- add[r[i] + 1] -= a[i];
- }
- if (i % maxK == 0 || i == q) {
- ll s = 0;
- for (int j = 1; j <= m; j++) {
- s += add[j];
- add[j] = 0;
- need[o[j]] -= s;
- }
- for (int j = 1; j <= n; j++) {
- if (start[j] == INF && need[j] <= 0) {
- startNeed[j] = need[j];
- start[j] = i;
- }
- }
- }
- }
- for (int i = 1; i <= n; i++) { // O((m + n) * maxK)
- if (start[i] == INF) {
- cout << "NIE" << endl;
- continue;
- }
- int j = start[i];
- ll s = startNeed[i];
- while (s <= 0 && j > 0) {
- for (int ii = 0; ii < (int)pos[i].size(); ii++) {
- int x = pos[i][ii];
- if (l[j] > r[j] && (x >= l[j] || x <= r[j])) {
- s += a[j];
- }
- if (l[j] <= r[j] && (x >= l[j] && x <= r[j])) {
- s += a[j];
- }
- }
- j--;
- }
- cout << j + 1 << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement