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);
}
};
//}}}
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<int32_t> O(M), P(N);
for (auto &x : O) cin >> x, x--;
for (auto &x : P) cin >> x;
vector<vector<int32_t>> S(N);
for (int i = 0; i < M; i++)
S[O[i]].push_back(i);
int K;
cin >> K;
vector<array<int32_t, 3>> Q(K);
for (auto &[l, r, a] : Q) {
cin >> l >> r >> a;
l--, r--;
}
vector<vector<int32_t>> who(K+1);
vector<int32_t> L(N, 0), R(N, K-1);
vector<int32_t> ans(N, -1);
for (int step = 0; step < LOG; step++) {
for (int i = 0; i < N; i++) {
if (L[i] > R[i]) continue;
int mid = (L[i]+R[i])/2;
who[mid].push_back(i);
}
RangeFenwick FT(M);
for (int mid = 0; mid < K; mid++) {
auto [l, r, x] = Q[mid];
if (l <= r) {
FT.update(l, r, x);
} else {
FT.update(l, M-1, x);
FT.update(0, r, x);
}
for (auto v : who[mid]) {
int sum = 0;
for (auto s : S[v]) {
sum += FT.query(s);
if (sum >= P[v]) break;
}
if (sum >= P[v]) {
ans[v] = mid;
R[v] = mid-1;
} else {
L[v] = mid+1;
}
}
who[mid].clear();
}
}
for (auto x : ans) {
if (x == -1) cout << "NIE" << endl;
else cout << x+1 << endl;
}
}
Compilation message (stderr)
met.cpp: In function 'void db(const A& ...)':
met.cpp:51:66: warning: fold-expressions only available with '-std=c++17' or '-std=gnu++17'
51 | template<typename ...A> void db(A const&... a) { ((cout << (a)), ...); cout << endl; }
| ^~~
met.cpp: In function 'int main()':
met.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
72 | for (auto &[l, r, a] : Q) {
| ^
met.cpp:90:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
90 | auto [l, r, x] = Q[mid];
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |