結果
問題 | No.1074 増殖 |
ユーザー | KoD |
提出日時 | 2020-06-05 22:25:46 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 8,054 bytes |
コンパイル時間 | 597 ms |
コンパイル使用メモリ | 75,652 KB |
最終ジャッジ日時 | 2023-08-22 16:12:59 |
合計ジャッジ時間 | 1,205 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:210:32: エラー: ‘numeric_limits’ is not a member of ‘std’ 210 | value_type identity = std::numeric_limits<T>::min(); | ^~~~~~~~~~~~~~ main.cpp:210:48: エラー: expected primary-expression before ‘>’ token 210 | value_type identity = std::numeric_limits<T>::min(); | ^ main.cpp:210:51: エラー: ‘::min’ has not been declared; did you mean ‘std::min’? 210 | value_type identity = std::numeric_limits<T>::min(); | ^~~ | std::min 次のファイルから読み込み: /usr/local/gcc7/include/c++/12.2.0/algorithm:61, 次から読み込み: main.cpp:3: /usr/local/gcc7/include/c++/12.2.0/bits/stl_algo.h:5736:5: 備考: ‘std::min’ declared here 5736 | min(initializer_list<_Tp> __l, _Compare __comp) | ^~~
ソースコード
#include <iostream> #include <algorithm> #include <utility> #include <numeric> #include <vector> #include <array> template <class T, class U> inline bool chmin(T &lhs, const U &rhs) { if (lhs > rhs) { lhs = rhs; return true; } return false; } template <class T, class U> inline bool chmax(T &lhs, const U &rhs) { if (lhs < rhs) { lhs = rhs; return true; } return false; } struct range { using itr = int64_t; struct iterator { itr i; constexpr iterator(itr i_): i(i_) { } constexpr void operator ++ () { ++i; } constexpr itr operator * () const { return i; } constexpr bool operator != (iterator x) const { return i != x.i; } }; const iterator l, r; constexpr range(itr l_, itr r_): l(l_), r(std::max(l_, r_)) { } constexpr iterator begin() const { return l; } constexpr iterator end() const { return r; } }; struct revrange { using itr = int64_t; struct iterator { itr i; constexpr iterator(itr i_): i(i_) { } constexpr void operator ++ () { --i; } constexpr itr operator * () const { return i; } constexpr bool operator != (iterator x) const { return i != x.i; } }; const iterator l, r; constexpr revrange(itr l_, itr r_): l(l_ - 1), r(std::max(l_, r_) - 1) { } constexpr iterator begin() const { return r; } constexpr iterator end() const { return l; } }; template <class T> class lazy_propagation_segment_tree { public: using value_type = typename T::value_type; using effector_type = typename T::effector_type; static inline const auto op1 = typename T::value_operation(); static inline const auto op2 = typename T::effector_operation(); static inline const auto op3 = typename T::merge_operation(); private: int size, height; std::vector<value_type> node; std::vector<effector_type> lazy; value_type fetch(int i, int l) const { if (lazy[i] == op2.identity) return node[i]; return op3(node[i], lazy[i], l); } void apply(int i, int l) { if (lazy[i] == op2.identity) return; if (i < size) { lazy[i << 1 | 0] = op2(lazy[i << 1 | 0], lazy[i]); lazy[i << 1 | 1] = op2(lazy[i << 1 | 1], lazy[i]); } node[i] = op3(node[i], lazy[i], l); lazy[i] = op2.identity; } void update() { for (int i = size - 1; i > 0; --i) { node[i] = op1(node[i << 1 | 0], node[i << 1 | 1]); } } void flush(int i) { for (int k = height; k >= 0; --k) { apply(i >> k, 1 << k); } } void lift(int i) { i >>= 1; int l = 1; while (i > 0) { node[i] = op1(fetch(i << 1 | 0, l), fetch(i << 1 | 1, l)); i >>= 1; l <<= 1; } } public: lazy_propagation_segment_tree() = default; lazy_propagation_segment_tree(int size_, const value_type &initial_ = op1.identity) { init(size_, initial_); } lazy_propagation_segment_tree(const std::vector<value_type> &node_) { build(node_); } void init(int size_, const value_type &initial_ = op1.identity) { size = 1; height = 0; while (size < size_) { size <<= 1; ++height; } node.assign(size << 1, initial_); lazy.assign(size << 1, op2.identity); update(); } void build(const std::vector<value_type> &node_) { init(node_.size()); for (int i = 0; i < node_.size(); ++i) { node[i + size] = node_[i]; } update(); } void assign(int i, const value_type &x) { i += size; flush(i); node[i] = x; lift(i); } void modify(int l, int r, const effector_type &x) { if (l >= r) return; flush(l + size); flush(r + size - 1); int tl = l + size, tr = r + size, k = 1; while (tl < tr) { if (tl & 1) { lazy[tl] = op2(lazy[tl], x); apply(tl, k); ++tl; } if (tr & 1) { --tr; lazy[tr] = op2(lazy[tr], x); apply(tr, k); } tl >>= 1; tr >>= 1; k <<= 1; } lift(l + size); lift(r + size - 1); } value_type fold(int l, int r) { if (l >= r) return op1.identity; flush(l + size); flush(r + size - 1); int tl = l + size, tr = r + size, k = 1; value_type resl = op1.identity, resr = op1.identity; while (tl < tr) { if (tl & 1) { apply(tl, k); resl = op1(resl, node[tl]); ++tl; } if (tr & 1) { --tr; apply(tr, k); resr = op1(node[tr], resr); } tl >>= 1; tr >>= 1; k <<= 1; } return op1(resl, resr); } }; template <class T> struct range_sum_range_assign { using value_type = std::pair<T, T>; using effector_type = T; struct value_operation { value_type identity = std::make_pair(0, 0); value_type operator () (const value_type &x, const value_type &y) const { return { x.first + y.first, x.second + y.second }; } }; struct effector_operation { effector_type identity = 0; effector_type operator () (const effector_type, const effector_type &y) const { return y; } }; struct merge_operation { value_type operator () (const value_type &x, const effector_type &y, int) const { return { y * x.second, x.second }; } }; }; template <class T> struct range_max_range_assign { using value_type = T; using effector_type = T; struct value_operation { value_type identity = std::numeric_limits<T>::min(); value_type operator () (const value_type &x, const value_type &y) const { return x > y ? x : y; } }; struct effector_operation { effector_type identity = 0; effector_type operator () (const effector_type, const effector_type &y) const { return y; } }; struct merge_operation { value_type operator () (const value_type, const effector_type &y, int) const { return y; } }; }; using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; constexpr i32 inf32 = (i32(1) << 30) - 1; constexpr i64 inf64 = (i64(1) << 62) - 1; std::vector<u32> solve(std::vector<u32> X, std::vector<u32> Y) { size_t N = X.size(); std::vector<u32> cmp; cmp.reserve(N + 1); cmp.push_back(0); for (auto x: X) { cmp.push_back(x); } std::sort(cmp.begin(), cmp.end()); cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end()); for (auto &x: X) { x = std::lower_bound(cmp.cbegin(), cmp.cend(), x) - cmp.cbegin() - 1; } size_t xs = cmp.size() - 1; lazy_propagation_segment_tree<range_sum_range_assign<u32>> sum; lazy_propagation_segment_tree<range_max_range_assign<u32>> max(xs); { std::vector<std::pair<u32, u32>> build(xs); for (auto i: range(0, xs)) { build[i].second = cmp[i + 1] - cmp[i]; } sum.build(build); } std::vector<u32> res(N); for (auto i: range(0, N)) { auto idx = [&]() -> u32 { if (max.fold(0, X[i] + 1) < Y[i]) { return 0; } if (max.fold(X[i], X[i] + 1) >= Y[i]) { return X[i] + 1; } u32 ok = X[i], ng = 0; while (ok - ng > 1) { u32 md = (ok + ng) >> 1; (max.fold(md, X[i] + 1) < Y[i] ? ok : ng) = md; } return ok; }(); if (idx == X[i] + 1) { // std::cout << 0 << ' '; continue; } u32 cur = sum.fold(idx, X[i] + 1).first; sum.modify(idx, X[i] + 1, Y[i]); max.modify(idx, X[i] + 1, Y[i]); u32 next = sum.fold(idx, X[i] + 1).first; res[i] = next - cur; // std::cout << res[i] << ' '; } // std::cout << '\n'; return res; } int main() { size_t N; std::cin >> N; std::array<std::vector<u32>, 4> X; X.fill(std::vector<u32>(N)); std::array<std::vector<u32>, 4> Y; Y.fill(std::vector<u32>(N)); for (auto i: range(0, N)) { i32 x1, y1, x2, y2; std::cin >> x1 >> y1 >> x2 >> y2; X[0][i] = X[3][i] = x2; X[1][i] = X[2][i] = -x1; Y[0][i] = Y[1][i] = y2; Y[2][i] = Y[3][i] = -y1; } std::array<std::vector<u32>, 4> ans; for (auto i: range(0, 4)) { ans[i] = solve(X[i], Y[i]); } for (auto i: range(0, N)) { u32 tmp = 0; for (auto j: range(0, 4)) { tmp += ans[j][i]; } std::cout << tmp << '\n'; } return 0; }