# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1046444 | qrno | Meteors (POI11_met) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
//{{{ FenwickTree
struct FenwickTree {
int N;
vector<int> data;
FenwickTree(int N) : N(N), data(N) {}
void add(int idx, int delta) {
for (; idx < N; idx |= idx+1)
data[idx] += delta;
}
int sum(int r) {
int ret = 0;
for (; r >= 0; r &= r+1, r--)
ret += data[r];
return ret;
}
int sum(int l, int r) {
return sum(r) - sum(l-1);
}
};
//}}}
// Range Fenwick {{{
struct RangeFenwick {
FenwickTree FT;
RangeFenwick(int N) : FT(N+1) {}
void update(int l, int r, int x) {
FT.add(l, x);
FT.add(r+1, -x);
}
int query(int idx) {
return FT.sum(idx);
}
};
//}}}
struct CircularFenwick {/*{{{*/
int N;
RangeFenwick RF;
CircularFenwick (int N) : N(N), RF(N) {}
void update(int l, int r, int x) {
if (l <= r) RF.update(l, r, x);
else {
RF.update(l, N-1, x);
RF.update(0, r, x);
}
}
int query(int idx) {
return RF.query(idx);
}
};/*}}}*/
const int LOG = 20;
// Debug {{{
#define var(x) "[", #x, " ", x, "] "
template<typename ...A> void db(A const&... a) { ((cout << (a)), ...); cout << endl; }
//}}}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> O(M), P(N);
for (auto &x : O) cin >> x, x--;
for (auto &x : P) cin >> x;
vector<vector<int>> S(N);
for (int i = 0; i < M; i++) {
S[O[i]].push_back(i);
}
int K;
cin >> K;
vector<array<int, 3>> Q(K);
for (auto &[l, r, a] : Q) {
cin >> l >> r >> a;
l--, r--;
}
vector<vector<int>> who(K+1);
vector<int> L(N, 0), R(N, K-1);
vector<int> ans(N, -1);
for (int step = 0; step < LOG; step++) {
for (int i = 0; i < N; i++) {
int mid = midpoint(L[i], R[i]);
who[mid].push_back(i);
}
/* db(var(step)); */
/* for (int i = 0; i < N; i++) { */
/* db(var(i), var(L[i]), var(R[i]), var(ans[i])); */
/* } */
CircularFenwick FT(M);
for (int mid = 0; mid < K; mid++) {
auto [l, r, x] = Q[mid];
FT.update(l, r, x);
for (auto v : who[mid]) {
int sum = 0;
for (auto s : S[v]) {
sum += FT.query(s);
}
if (sum >= P[v]) {
ans[v] = mid;
R[v] = mid-1;
} else {
L[v] = mid+1;
}
/* db(var(mid), var(v), var(sum), var(P[v])); */
}
who[mid].clear();
}
}
for (auto x : ans) {
if (x == -1) cout << "NIE" << endl;
else cout << x+1 << endl;
}
}