You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
93 lines
2.5 KiB
93 lines
2.5 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
typedef long long ll;
|
|
typedef unsigned long long ull;
|
|
const int N = 6e5 + 5, M = 2e4 + 5, inf = 0x3f3f3f3f, mod = 1e9 + 7;
|
|
#define mst(a, b) memset(a, b, sizeof a)
|
|
#define PII pair<int, int>
|
|
#define fi first
|
|
#define se second
|
|
#define pb emplace_back
|
|
#define SZ(a) (int)a.size()
|
|
#define IOS ios::sync_with_stdio(false), cin.tie(0)
|
|
void Print(int *a, int n) {
|
|
for (int i = 1; i < n; i++)
|
|
printf("%d ", a[i]);
|
|
printf("%d\n", a[n]);
|
|
}
|
|
int n, m, k;
|
|
struct BIT {
|
|
#define lowbit(x) x &(-x)
|
|
#define il inline
|
|
ll s[N];
|
|
int n;
|
|
il void upd(int x, int v) {
|
|
while (x <= 2 * m) {
|
|
s[x] += v;
|
|
x += lowbit(x);
|
|
}
|
|
return;
|
|
}
|
|
il ll que(int x) {
|
|
ll ans = 0;
|
|
while (x) {
|
|
ans += s[x];
|
|
x -= lowbit(x);
|
|
}
|
|
return ans;
|
|
}
|
|
} T;
|
|
vector<int> a[N];
|
|
struct node {
|
|
int x, id;
|
|
} p[N], p1[N], p2[N];
|
|
struct query {
|
|
int l, r, x;
|
|
} q[N];
|
|
int ans[N];
|
|
void solve(int l, int r, int ql, int qr) {
|
|
if (ql > qr) return;
|
|
if (l == r) {
|
|
for (int i = ql; i <= qr; i++) ans[p[i].id] = l;
|
|
return;
|
|
}
|
|
int mid = (l + r) >> 1;
|
|
int c1 = 0, c2 = 0;
|
|
for (int i = l; i <= mid; i++) T.upd(q[i].l, q[i].x), T.upd(q[i].r + 1, -q[i].x);
|
|
for (int i = ql; i <= qr; i++) {
|
|
ll s = 0;
|
|
int u = p[i].id;
|
|
for (int j : a[u]) {
|
|
s += T.que(j) + T.que(j + m);
|
|
if (s >= p[i].x) break;
|
|
}
|
|
if (s >= p[i].x)
|
|
p1[++c1] = p[i];
|
|
else
|
|
p[i].x -= s, p2[++c2] = p[i];
|
|
}
|
|
for (int i = 1; i <= c1; i++) p[ql + i - 1] = p1[i];
|
|
for (int i = 1; i <= c2; i++) p[ql + i + c1 - 1] = p2[i];
|
|
for (int i = l; i <= mid; i++) T.upd(q[i].l, -q[i].x), T.upd(q[i].r + 1, q[i].x);
|
|
solve(l, mid, ql, ql + c1 - 1), solve(mid + 1, r, ql + c1, qr);
|
|
}
|
|
int main() {
|
|
scanf("%d%d", &n, &m);
|
|
for (int i = 1, x; i <= m; i++)
|
|
scanf("%d", &x), a[x].pb(i);
|
|
for (int i = 1; i <= n; i++) scanf("%d", &p[i].x), p[i].id = i;
|
|
scanf("%d", &k);
|
|
for (int i = 1; i <= k; i++) {
|
|
scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].x);
|
|
if (q[i].l > q[i].r) q[i].r += m;
|
|
}
|
|
q[++k].l = 1, q[k].r = 2 * m, q[k].x = inf;
|
|
solve(1, k, 1, n);
|
|
for (int i = 1; i <= n; i++)
|
|
if (ans[i] == k)
|
|
puts("NIE");
|
|
else
|
|
printf("%d\n", ans[i]);
|
|
return 0;
|
|
}
|