// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;}
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#pragma GCC optimize("Ofast")
#define debug(...) ((void)0)
#endif
const int kN = 300003;
int n, m, o[kN], p[kN];
int k, l[kN], r[kN], a[kN];
int ans[kN];
struct SGT {
int n; vector<ll> val;
SGT (int nn = 0): n(nn), val(nn+1, 0) {}
void modify(int p, int v) {
for (; p <= n; p += p & -p)
val[p] += v;
}
ll query(int p) {
ll r = 0;
for (; p > 0; p -= p & -p)
r += val[p];
return r;
}
void modify(int l, int r, int v) {
modify(l, v);
modify(r+1, -v);
}
} sgt;
ll tmp[kN];
int cnt[kN];
void pbs(vector<int> &ids, int ql, int qr) {
if (ql == qr) {
for (int &i: ids)
ans[o[i]] = ql;
return;
}
int qm = (ql + qr) / 2;
for (int i = ql + (ql == 0); i <= qm; ++i) {
if (l[i] <= r[i]) sgt.modify(l[i], r[i], a[i]);
else {
sgt.modify(l[i], m, a[i]);
sgt.modify(1, r[i], a[i]);
}
}
for (int &i: ids) {
tmp[o[i]] += sgt.query(i);
++cnt[o[i]];
}
vector<int> lid, rid;
for (int &i: ids) {
--cnt[o[i]];
if (tmp[o[i]] >= p[o[i]]) {
lid.pb(i);
} else {
rid.pb(i);
if (cnt[o[i]] == 0)
p[o[i]] -= tmp[o[i]];
}
if (cnt[o[i]] == 0)
tmp[o[i]] = 0;
}
for (int i = ql + (ql == 0); i <= qm; ++i) {
if (l[i] <= r[i]) sgt.modify(l[i], r[i], -a[i]);
else {
sgt.modify(l[i], m, -a[i]);
sgt.modify(1, r[i], -a[i]);
}
}
if (!lid.empty()) pbs(lid, ql, qm);
if (!rid.empty()) pbs(rid, qm+1, qr);
}
void solve() {
for (int i = 1; i <= n; ++i)
ans[i] = k+1;
vector<int> ids(m);
iota(AI(ids), 1);
sgt = SGT(m);
pbs(ids, 0, k+1);
}
void input() {
assert(cin >> n >> m);
for (int i = 1; i <= m; ++i) assert(cin >> o[i]);
for (int i = 1; i <= n; ++i) assert(cin >> p[i]);
assert(cin >> k);
for (int i = 1; i <= k; ++i)
assert(cin >> l[i] >> r[i] >> a[i]);
assert(1 <= n and n <= kN);
assert(1 <= m and m <= kN);
for (int i = 1; i <= m; ++i) assert(1 <= o[i] and o[i] <= n);
for (int i = 1; i <= n; ++i) assert(1 <= p[i] and p[i] <= 1e9);
for (int i = 1; i <= k; ++i) {
assert (1 <= l[i] and l[i] <= m);
assert (1 <= r[i] and r[i] <= m);
assert (1 <= a[i] and a[i] <= 1e9);
}
}
void ouput() {
for (int i = 1; i <= n; ++i) {
if (ans[i] == k+1) cout << "NIE\n";
else cout << ans[i] << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
input();
solve();
ouput();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
4204 KB |
Output is correct |
2 |
Correct |
60 ms |
5248 KB |
Output is correct |
3 |
Correct |
77 ms |
2620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
78 ms |
2576 KB |
Output is correct |
2 |
Correct |
76 ms |
2512 KB |
Output is correct |
3 |
Correct |
57 ms |
4440 KB |
Output is correct |
4 |
Correct |
27 ms |
3136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
62 ms |
2984 KB |
Output is correct |
2 |
Correct |
72 ms |
4488 KB |
Output is correct |
3 |
Correct |
17 ms |
1040 KB |
Output is correct |
4 |
Correct |
80 ms |
2936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
46 ms |
3880 KB |
Output is correct |
2 |
Correct |
78 ms |
3944 KB |
Output is correct |
3 |
Correct |
60 ms |
2660 KB |
Output is correct |
4 |
Correct |
88 ms |
3476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
396 ms |
25536 KB |
Output is correct |
2 |
Incorrect |
320 ms |
21572 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
382 ms |
22232 KB |
Output is correct |
2 |
Incorrect |
318 ms |
18464 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |