1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define maxn 300010
#define lowbit(i) ((i) & (-i))
#define ll long long
#define INF 1000000000
using namespace std;
int n, m, k, p[maxn];
vector<int> d[maxn];
struct node {
int l, r, v;
} a[maxn];
ll Bit[maxn];
void add(int i, int v) { while (i <= n) Bit[i] += v, i += lowbit(i); }
ll get_sum(int i) {
ll s = 0;
while (i) s += Bit[i], i -= lowbit(i);
return s;
}
int now;
void update(int k) {
while (now > k) {
int l = a[now].l, r = a[now].r, v = -a[now].v; --now;
if (l > r) add(l, v), add(n + 1, -v), add(1, v), add(r + 1, -v);
else add(l, v), add(r + 1, -v);
}
while (now < k) {
++now; int l = a[now].l, r = a[now].r, v = a[now].v;
if (l > r) add(l, v), add(n + 1, -v), add(1, v), add(r + 1, -v);
else add(l, v), add(r + 1, -v);
}
}
int Q[maxn], t1[maxn], t2[maxn], ans[maxn];
void solve(int l, int r, int L, int R) {
if (L > R) return ;
if (l == r) {
for (int i = L; i <= R; ++i) ans[Q[i]] = l;
return ;
} int m = l + r >> 1, c1 = 0, c2 = 0; update(m);
for (int i = L; i <= R; ++i) {
ll s = 0;
for (auto t : d[Q[i]]) s += get_sum(t), s = min(s, (ll) p[Q[i]]);
if (p[Q[i]] <= s) t1[++c1] = Q[i];
else t2[++c2] = Q[i];
}
for (int i = 1; i <= c1; ++i) Q[L + i - 1] = t1[i];
for (int i = 1; i <= c2; ++i) Q[L + c1 + i - 1] = t2[i];
solve(l, m, L, L + c1 - 1); solve(m + 1, r, L + c1, R);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> m >> n;
for (int i = 1; i <= n; ++i) {
int x; cin >> x;
d[x].push_back(i);
}
for (int i = 1; i <= m; ++i) cin >> p[i], Q[i] = i;
cin >> k;
for (int i = 1; i <= k; ++i) cin >> a[i].l >> a[i].r >> a[i].v;
a[k + 1] = { 1, n, INF };
solve(1, k + 1, 1, m);
for (int i = 1; i <= m; ++i)
ans[i] == k + 1 ? cout << "NIE\n" : cout << ans[i] << "\n";
return 0;
}
|