test/aoj/3165/main.test.imos.cpp
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3165"
#include <iostream>
#include "Mylib/Algorithm/linear_imos_1d.cpp"
#include "Mylib/IO/input_tuples.cpp"
#include "Mylib/IO/join.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, Q;
std::cin >> N >> Q;
auto imos = hl::linear_imos_1d<int64_t>(N);
for (auto [l, k] : hl::input_tuples<int, int>(Q)) {
--l;
imos.update(l, l + k, 1, 1);
}
const auto res = imos.build();
std::cout << hl::join(res.begin(), res.end()) << "\n";
return 0;
}
#line 1 "test/aoj/3165/main.test.imos.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3165"
#include <iostream>
#line 2 "Mylib/Algorithm/linear_imos_1d.cpp"
#include <cassert>
#include <vector>
namespace haar_lib {
template <typename T>
class linear_imos_1d {
public:
using value_type = T;
private:
int n_;
std::vector<T> vec_a_, vec_a_end_, vec_b_;
public:
linear_imos_1d(int n) : n_(n), vec_a_(n_ + 1), vec_a_end_(n_ + 1), vec_b_(n_ + 1) {}
void update(int s, int t, const T &a, const T &b) {
assert(0 <= s and s <= t and t <= n_);
vec_a_[s + 1] += a;
vec_a_[t] -= a;
vec_a_end_[t] -= a * (t - s - 1);
vec_b_[s] += b;
vec_b_[t] -= b;
}
auto build() const {
std::vector<T> ret(vec_a_);
for (int i = 0; i < n_; ++i) ret[i + 1] += ret[i];
for (int i = 0; i < n_; ++i) ret[i] += vec_a_end_[i];
for (int i = 0; i < n_; ++i) ret[i + 1] += ret[i];
std::vector<T> temp(vec_b_);
for (int i = 0; i < n_; ++i) temp[i + 1] += temp[i];
for (int i = 0; i < n_; ++i) ret[i] += temp[i];
ret.pop_back();
return ret;
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples.cpp"
#include <tuple>
#include <utility>
#line 6 "Mylib/IO/input_tuple.cpp"
namespace haar_lib {
template <typename T, size_t... I>
static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
}
template <typename T, typename U>
std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
s >> value.first >> value.second;
return s;
}
template <typename... Args>
std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
return s;
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuples {
struct iter {
using value_type = std::tuple<Args...>;
value_type value;
bool fetched = false;
int N, c = 0;
value_type operator*() {
if (not fetched) {
std::cin >> value;
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuples(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples(int N) {
return InputTuples<Args...>(N);
}
} // namespace haar_lib
#line 3 "Mylib/IO/join.cpp"
#include <sstream>
#include <string>
namespace haar_lib {
template <typename Iter>
std::string join(Iter first, Iter last, std::string delim = " ") {
std::stringstream s;
for (auto it = first; it != last; ++it) {
if (it != first) s << delim;
s << *it;
}
return s.str();
}
} // namespace haar_lib
#line 7 "test/aoj/3165/main.test.imos.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, Q;
std::cin >> N >> Q;
auto imos = hl::linear_imos_1d<int64_t>(N);
for (auto [l, k] : hl::input_tuples<int, int>(Q)) {
--l;
imos.update(l, l + k, 1, 1);
}
const auto res = imos.build();
std::cout << hl::join(res.begin(), res.end()) << "\n";
return 0;
}
Back to top page