//Bismillahir-Rahmanir-Rahim
# include <bits/stdc++.h>
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x << " = " << x << endl;
# define pll pair <ll, ll>
# define pii pair <int, int>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll maxn = 3e5 + 25;
const ll inf = 2e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
const ll P = 67;
using namespace std;
int n, m, q, tl[maxn], tr[maxn];
vector <int> boss[maxn];
int need[maxn], ans[maxn];
int l[maxn], r[maxn];
ll a[maxn];
vector <int> check[maxn];
struct fenwick
{
ll t[maxn];
void clear ()
{
for (int i = 1; i <= m; ++i)
{
t[i] = 0;
}
}
void update (int id, ll x)
{
for (; id < maxn; id += (id & (-id)))
{
t[id] += x;
}
}
ll get (int id)
{
ll res = 0;
for (; id >= 1; id -= (id & (-id)))
{
res += t[id];
}
return res;
}
} t;
void ma1n (/* SABR */)
{
cin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int owner;
cin >> owner;
boss[owner].pb(i);
}
for (int i = 1; i <= n; ++i)
{
cin >> need[i];
}
cin >> q;
for (int i = 1; i <= q; ++i)
{
cin >> l[i] >> r[i] >> a[i];
}
for (int i = 1; i <= n; ++i)
{
tl[i] = 1, tr[i] = q, ans[i] = -1;
}
bool boo = 1;
while (boo)
{
boo = 0;
t.clear();
for (int i = 1; i <= n; ++i)
{
if (tl[i] <= tr[i])
{
check[(tl[i] + tr[i]) >> 1].pb(i);
}
// cout << tl[i] << ' ' << tr[i] << nl;
}
for (int i = 1; i <= q; ++i)
{
if (l[i] <= r[i])
{
t.update(l[i], a[i]);
t.update(r[i] + 1, -a[i]);
}
else
{
t.update(1, a[i]);
t.update(r[i] + 1, -a[i]);
t.update(l[i], a[i]);
}
while (!check[i].empty())
{
boo = 1;
int id = check[i].back();
check[i].pop_back();
ll sum = 0;
for (int x : boss[id])
{
sum += t.get(x);
if (sum >= need[id]) break;
}
if (sum >= need[id])
{
tr[id] = i - 1;
ans[id] = i;
}
else
{
tl[id] = i + 1;
}
}
}
}
for (int i = 1; i <= n; ++i)
{
if (ans[i] == -1)
{
cout << "NIE" << nl;
}
else
{
cout << ans[i] << nl;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
int ttt = 1;
// cin >> ttt;
for (int test = 1; test <= ttt; ++test)
{
// cout << "Case " << test << ":" << '\n';
ma1n();
}
return 0;
}
// 998batrr | BbIWEJI 3A TObOU!!!
// tourist | BbIWEJI 3A TObOU!!!
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
14552 KB |
Output is correct |
2 |
Correct |
12 ms |
14676 KB |
Output is correct |
3 |
Correct |
9 ms |
14548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
14576 KB |
Output is correct |
2 |
Correct |
8 ms |
14548 KB |
Output is correct |
3 |
Correct |
9 ms |
14548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
64 ms |
17100 KB |
Output is correct |
2 |
Correct |
121 ms |
19308 KB |
Output is correct |
3 |
Correct |
100 ms |
18860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
102 ms |
18224 KB |
Output is correct |
2 |
Correct |
101 ms |
18276 KB |
Output is correct |
3 |
Correct |
119 ms |
19352 KB |
Output is correct |
4 |
Correct |
27 ms |
17228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
99 ms |
17600 KB |
Output is correct |
2 |
Correct |
163 ms |
19980 KB |
Output is correct |
3 |
Correct |
108 ms |
15872 KB |
Output is correct |
4 |
Correct |
93 ms |
19376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
16856 KB |
Output is correct |
2 |
Correct |
115 ms |
18280 KB |
Output is correct |
3 |
Correct |
69 ms |
17112 KB |
Output is correct |
4 |
Correct |
116 ms |
20632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
833 ms |
36488 KB |
Output is correct |
2 |
Correct |
653 ms |
23988 KB |
Output is correct |
3 |
Correct |
668 ms |
19164 KB |
Output is correct |
4 |
Correct |
1475 ms |
57372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
829 ms |
35048 KB |
Output is correct |
2 |
Correct |
672 ms |
24148 KB |
Output is correct |
3 |
Correct |
463 ms |
18524 KB |
Output is correct |
4 |
Correct |
1685 ms |
61272 KB |
Output is correct |