#include <bits/stdc++.h>
#include <cassert>
#include <vector>
#include <cassert>
#include <numeric>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
template <class T> struct fenwick_tree {
using U = internal::to_unsigned_t<T>;
public:
fenwick_tree() : _n(0) {}
explicit fenwick_tree(int n) : _n(n), data(n) {}
void add(int p, T x) {
assert(0 <= p && p < _n);
p++;
while (p <= _n) {
data[p - 1] += U(x);
p += p & -p;
}
}
T sum(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
return sum(r) - sum(l);
}
private:
int _n;
std::vector<U> data;
U sum(int r) {
U s = 0;
while (r > 0) {
s += data[r - 1];
r -= r & -r;
}
return s;
}
};
} // namespace atcoder
using namespace std;
using namespace atcoder;
auto main() -> int {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int N, M;
cin >> N >> M;
vector<vector<int>> g(N);
for (int i = 0; i < M; i++) {
int o;
cin >> o;
g[o-1].push_back(i);
}
vector<int64_t> p(N);
for (auto& x : p) {
cin >> x;
}
int Q;
cin >> Q;
vector<tuple<int, int, int64_t>> vec(Q);
for (auto& [l, r, a] : vec) {
cin >> l >> r >> a;
--l, --r;
}
vector<pair<int, int>> rng(N, make_pair(0, Q));
while (any_of(begin(rng), end(rng), [](auto e) { return e.first < e.second; })) {
vector<vector<int>> t(Q+1);
for (int i = 0; i < N; i++) {
auto [lo, hi] = rng[i];
if (lo < hi) {
auto mid = (lo + hi) / 2;
t[mid].push_back(i);
}
}
fenwick_tree<int64_t> ft(M+1);
auto update = [&](int l, int r, int64_t val) {
ft.add(l, val);
ft.add(r+1, -val);
};
auto query = [&](int pos) {
return ft.sum(0, pos+1);
};
for (int i = 0; i < Q; i++) {
auto [l, r, a] = vec[i];
if (l <= r) {
update(l, r, a);
} else {
update(l, M-1, a);
update(0, r, a);
}
for (auto v : t[i]) {
__int128 sum = 0;
for (auto x : g[v]) {
sum += query(x);
}
auto& [lo, hi] = rng[v];
if (sum >= p[v]) {
hi = i;
} else {
lo = i + 1;
}
}
}
}
for (auto [lo, hi] : rng) {
if (lo == Q) {
cout << "NIE\n";
} else {
cout << lo + 1 << '\n';
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
432 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
59 ms |
3236 KB |
Output is correct |
| 2 |
Correct |
105 ms |
4628 KB |
Output is correct |
| 3 |
Correct |
92 ms |
4060 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
84 ms |
3672 KB |
Output is correct |
| 2 |
Correct |
83 ms |
3680 KB |
Output is correct |
| 3 |
Correct |
98 ms |
4596 KB |
Output is correct |
| 4 |
Correct |
33 ms |
2376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
63 ms |
3360 KB |
Output is correct |
| 2 |
Correct |
76 ms |
4720 KB |
Output is correct |
| 3 |
Correct |
42 ms |
2320 KB |
Output is correct |
| 4 |
Correct |
97 ms |
4308 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
83 ms |
2996 KB |
Output is correct |
| 2 |
Correct |
93 ms |
3736 KB |
Output is correct |
| 3 |
Correct |
66 ms |
3080 KB |
Output is correct |
| 4 |
Correct |
102 ms |
4908 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
898 ms |
23680 KB |
Output is correct |
| 2 |
Correct |
523 ms |
15672 KB |
Output is correct |
| 3 |
Correct |
240 ms |
10052 KB |
Output is correct |
| 4 |
Correct |
1548 ms |
32940 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
845 ms |
22884 KB |
Output is correct |
| 2 |
Correct |
579 ms |
15672 KB |
Output is correct |
| 3 |
Correct |
201 ms |
8132 KB |
Output is correct |
| 4 |
Correct |
1647 ms |
35684 KB |
Output is correct |
