// QuangBuiCP
// https://oj.uz/problem/view/POI11_met
#include "bits/stdc++.h"
using namespace std;
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif // LOCAL
int n, m;
cin >> n >> m;
vector<vector<int>> properties(n);
for (int i = 0; i < m; ++i) {
int who;
cin >> who;
properties[--who].push_back(i);
}
vector<int64_t> target(n);
for (int& it : target) {
cin >> it;
}
int events;
cin >> events;
vector<tuple<int, int, int64_t>> event(events);
for (auto& [l, r, collectable] : event) {
cin >> l >> r >> collectable;
l--, r--;
}
vector<vector<int>> candidates(events + 1);
vector<int> L(n, 0), R(n, events - 1);
vector<int> answer(n, -1);
for (int step = 0; step < 20; ++step) {
for (int i = 0; i < n; ++i) {
if (L[i] > R[i]) {
continue;
}
int mid = (L[i] + R[i]) / 2;
candidates[mid].push_back(i);
}
vector<int64_t> fenw(m + 1, 0);
auto Update = [&fenw, &m](int x, int64_t val) {
while (x <= m) {
fenw[x] += val;
x |= x + 1;
}
};
auto UpdateRange = [&fenw, &m, &Update](int l, int r, int64_t val) {
Update(l, val);
Update(r + 1, -val);
};
auto Query = [&fenw](int x) {
int64_t res = 0;
while (x >= 0) {
res += fenw[x];
x &= x + 1;
x--;
}
return res;
};
for (int mid = 0; mid < events; ++mid) {
auto [l, r, collectable] = event[mid];
if (l <= r) {
UpdateRange(l, r, collectable);
} else {
UpdateRange(l, m - 1, collectable);
UpdateRange(0, r, collectable);
}
for (int who : candidates[mid]) {
int64_t sum = 0;
for (int land : properties[who]) {
sum += Query(land);
}
if (sum >= target[who]) {
answer[who] = mid;
R[who] = mid - 1;
} else {
L[who] = mid + 1;
}
}
candidates[mid].clear();
}
}
for (int x : answer) {
if (x == -1) {
cout << "NIE\n";
} else {
cout << x + 1 << '\n';
}
}
return 0;
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:20:18: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
20 | for (int& it : target) {
| ^~~~~~
