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
| #include<cstdio>
#include<cstring>
#include<vector>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
inline int read()
{
int data = 0, w = 1;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data*w;
}
const int maxn(3e5 + 10);
struct node { int l, r; long long a; } r[maxn];
struct qry { int id; long long p; } p[maxn], pl[maxn], pr[maxn];
long long c[maxn]; std::vector<int> a[maxn];
int n, m, ans[maxn], K;
inline void add(int x, int v) { while(x <= m) c[x] += v, x += x & -x; }
inline long long query(int x) { long long ans = 0; while(x) ans += c[x], x -= x & -x; return ans; }
inline void fall(int x, int o)
{
if(r[x].l > r[x].r) add(1, o * r[x].a);
add(r[x].l, o * r[x].a); add(r[x].r + 1, -o * r[x].a);
}
inline bool check(int x, long long &sum)
{
sum = 0;
static std::vector<int>::iterator it;
for(it = a[p[x].id].begin(); it != a[p[x].id].end(); ++it) { sum += query(*it); if(sum >= p[x].p) return true; }
return false;
}
void Div(int l, int r, int ql, int qr)
{
if(ql > qr) return;
if(l == r) { for(RG int i = ql; i <= qr; i++) ans[p[i].id] = l; return; }
int mid = (l + r) >> 1, tl = 0, tr = 0;
long long sum;
for(RG int i = l; i <= mid; i++) fall(i, 1);
for(RG int i = ql; i <= qr; i++)
if(check(i, sum)) pl[++tl] = p[i];
else p[i].p -= sum, pr[++tr] = p[i];
for(RG int i = l; i <= mid; i++) fall(i, -1);
for(RG int i = 1; i <= tl; i++) p[i + ql - 1] = pl[i];
for(RG int i = 1; i <= tr; i++) p[i + ql + tl - 1] = pr[i];
Div(l, mid, ql, ql + tl - 1);
Div(mid + 1, r, ql + tl, qr);
}
int main()
{
#ifndef ONLINE_JUDGE
file(cpp);
#endif
n = read(); m = read();
for(RG int i = 1; i <= m; i++) a[read()].push_back(i);
for(RG int i = 1; i <= n; i++) p[i] = (qry) {i, read()};
K = read();
for(RG int i = 1; i <= K; i++) r[i] = (node) {read(), read(), read()};
r[++K] = (node) {1, m, 1000000000};
Div(1, K, 1, n);
for(RG int i = 1; i <= n; i++) ans[i] == K ? puts("NIE") : printf("%d\n", ans[i]);
return 0;
}
|