#define ll loli
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define push emplace
#define lb(x, v) lower_bound(all(x), v)
#define ub(x, v) upper_bound(all(x), v)
#define sz(x) (int)(x.size())
#define re(x) reverse(all(x))
#define uni(x) x.resize(unique(all(x)) - x.begin())
#define all(x) x.begin(), x.end()
#define mem(x, v) memset(x, v, sizeof x);
#define int long long
#define pii pair<int, int>
#define inf 1000000000
#define INF 1000000000000000000
#define mod 1000000007
#define F first
#define S second
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
#define chmax(a, b) (a = (b > a ? b : a))
#define chmin(a, b) (a = (b < a ? b : a))
#define get_bit(x, y) ((x>>y)&1)
#define mkp make_pair
using namespace std;
#ifdef loli
void trace_() {cerr << "\n";}
template<typename T1, typename... T2> void trace_(T1 t1, T2... t2) {cerr << ' ' << t1; trace_(t2...); }
#define trace(...) cerr << "[" << #__VA_ARGS__ << "] :", trace_(__VA_ARGS__);
#else
#define trace(...) 49
#endif
const int mxN = 3e5 + 5, mxA = 10000000000;
int n, m, k, ans[mxN];
unsigned int sum[mxN], a[mxN];
int tot;
array<int, 3> v[mxN * 5], tmp[mxN * 5];
bool cmp(array<int, 3> a, array<int, 3> b) {
if (a[1] == b[1]) return (a[0] == 0 ? INF : a[0]) < (b[0] == 0 ? INF : b[0]);
return a[1] < b[1];
}
void bs(int l, int r, int ql, int qr) {
if (l == r) {
for (int j = ql; j <= qr; j++) {
auto [i, p, o] = v[j];
if (!i) ans[o] = l;
}
return;
}
int mid = (l + r) / 2;
unsigned res = 0;
for (int j = ql; j <= qr; j++) {
auto [i, x, val] = v[j];
if (i and i <= mid) res += val;
if (!i) sum[val] += res;
}
int tl = ql, tr = qr;
for (int j = ql; j <= qr; j++) {
auto [i, x, val] = v[j];
if (i) {
if (i <= mid) tmp[tl++] = v[j];
else tmp[tr--] = v[j];
} else {
if (a[val] <= sum[val]) tmp[tl++] = v[j];
else tmp[tr--] = v[j];
}
}
reverse(tmp + tl, tmp + qr + 1);
copy(tmp + ql, tmp + qr + 1, v + ql);
res = 0;
for (int j = ql; j < tl; j++) {
auto [i, x, val] = v[j];
if (i) res += val;
else sum[val] -= res;
}
bs(l, mid, ql, tr);
bs(mid+1, r, tl, qr);
}
inline void solve() {
cin >> n >> m;
vector<int> o(m + 1);
for (int i = 1; i <= m; i++) cin >> o[i];
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) v[tot++] = {0, i, o[i]};
cin >> k;
for (int i = 1; i <= k; i++) {
int l, r, x; cin >> l >> r >> x;
if (l > r) {
v[tot++] = {i, l, x};
v[tot++] = {i, 1, x};
v[tot++] = {i, r + 1, -x};
} else {
v[tot++] = {i, l, x};
if (r + 1 <= m) v[tot++] = {i, r + 1, -x};
}
}
sort(v, v + tot, cmp);
bs(1, k + 1, 0, tot - 1);
for (int i = 1; i <= n; i++) {
if (ans[i] == 0 or ans[i] == k + 1) cout << "NIE\n";
else cout << ans[i] << '\n';
}
}
signed main() {
IO;
solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
7836 KB |
Output is correct |
2 |
Correct |
76 ms |
10100 KB |
Output is correct |
3 |
Correct |
85 ms |
8476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
77 ms |
9144 KB |
Output is correct |
2 |
Correct |
76 ms |
9140 KB |
Output is correct |
3 |
Correct |
84 ms |
10184 KB |
Output is correct |
4 |
Correct |
21 ms |
3944 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
7852 KB |
Output is correct |
2 |
Correct |
60 ms |
10700 KB |
Output is correct |
3 |
Correct |
52 ms |
6228 KB |
Output is correct |
4 |
Correct |
81 ms |
8500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
9556 KB |
Output is correct |
2 |
Correct |
74 ms |
9788 KB |
Output is correct |
3 |
Correct |
67 ms |
8124 KB |
Output is correct |
4 |
Correct |
106 ms |
9680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
537 ms |
54948 KB |
Output is correct |
2 |
Correct |
413 ms |
59048 KB |
Output is correct |
3 |
Correct |
255 ms |
32052 KB |
Output is correct |
4 |
Correct |
684 ms |
65536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
544 ms |
54536 KB |
Output is correct |
2 |
Correct |
273 ms |
44960 KB |
Output is correct |
3 |
Correct |
222 ms |
27256 KB |
Output is correct |
4 |
Correct |
605 ms |
65536 KB |
Output is correct |