結果
問題 | No.2657 Falling Block Game |
ユーザー |
|
提出日時 | 2024-03-01 22:12:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 10,707 bytes |
コンパイル時間 | 2,808 ms |
コンパイル使用メモリ | 261,928 KB |
実行使用メモリ | 11,904 KB |
最終ジャッジ日時 | 2024-09-29 14:12:42 |
合計ジャッジ時間 | 5,679 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
// #pragma GCC optimize("O3,unroll-loops")#include <bits/stdc++.h>// #include <x86intrin.h>using namespace std;#if __cplusplus >= 202002Lusing namespace numbers;#endiftemplate<bool HAS_QUERY, bool HAS_UPDATE, class T, class U, class F1, class F2, class F3>struct segment_tree_base{static_assert(HAS_QUERY || HAS_UPDATE);#ifdef LOCAL#define ASSERT(c) assert(c)#else#define ASSERT(c) 42#endif#define ifQ if constexpr(HAS_QUERY)#define ifU if constexpr(HAS_UPDATE)int n, size, log;vector<T> data;vector<U> data_action;F1 TT; // monoid operation (always adjacent)T T_id; // monoid identityF2 UU; // monoid operation (superset, subset)U U_id; // monoid identityF3 UT; // action of U on T (superset, subset)// O(n)segment_tree_base(F1 TT, T T_id, F2 UU, U U_id, F3 UT): TT(TT), T_id(T_id), UU(UU), U_id(U_id), UT(UT){ }segment_tree_base &operator=(const segment_tree_base &seg){n = seg.n;size = seg.size;log = seg.log;data = seg.data;data_action = seg.data_action;}// O(1)friend void swap(segment_tree_base &x, segment_tree_base &y){swap(x.n, y.n);swap(x.size, y.size);swap(x.log, y.log);swap(x.data, y.data);swap(x.data_action, y.data_action);}// O(n)void build(int n){ASSERT(n >= 0);this->n = n;size = 1;while(size < n) size <<= 1;log = __lg(size);ifQ data.assign(size << 1, T_id);ifU data_action.assign(HAS_QUERY ? size : size << 1, U_id);}// O(n)void build(int n, T x){static_assert(HAS_QUERY);ASSERT(n >= 0);this->n = n;size = 1;while(size < n) size <<= 1;log = __lg(size);data.assign(size << 1, T_id);fill(data.begin() + size, data.begin() + size + n, x);for(auto i = size - 1; i >= 1; -- i) refresh(i);ifU data_action.assign(size, U_id);}// O(n)template<class V>void build(const vector<V> &a){static_assert(HAS_QUERY);n = (int)a.size();size = 1;while(size < n) size <<= 1;log = __lg(size);data.assign(size << 1, T_id);copy(a.begin(), a.end(), data.begin() + size);for(auto i = size - 1; i >= 1; -- i) refresh(i);ifU data_action.assign(size, U_id);}// O(n)void build_action(int n){static_assert(!HAS_QUERY && HAS_UPDATE);ASSERT(n >= 0);build(n);}// O(n)void build_action(int n, U f){static_assert(!HAS_QUERY && HAS_UPDATE);ASSERT(n >= 0);this->n = n;size = 1;while(size < n) size <<= 1;log = __lg(size);data_action.assign(size << 1, U_id);fill(data_action.begin() + size, data_action.begin() + size + n, f);}// O(n)template<class V>void build_action(const vector<V> &a){static_assert(!HAS_QUERY && HAS_UPDATE);n = (int)a.size();size = 1;while(size < n) size <<= 1;log = __lg(size);data_action.assign(size << 1, U_id);copy(a.begin(), a.end(), data_action.begin() + size);}// O(1)void refresh(int u){static_assert(HAS_QUERY);data[u] = TT(data[u << 1], data[u << 1 | 1]);}// O(1)void apply(int u, U f){static_assert(HAS_UPDATE);ifQ data[u] = UT(f, data[u]);if(!HAS_QUERY || u < size) data_action[u] = UU(f, data_action[u]);}// O(1)void push(int u){static_assert(HAS_UPDATE);apply(u << 1, data_action[u]), apply(u << 1 | 1, data_action[u]);data_action[u] = U_id;}// O(log(n)) if HAS_UPDATE, O(1) otherwise.T query(int p){static_assert(HAS_QUERY);ASSERT(0 <= p && p < n);p += size;ifU for(auto i = log; i >= 1; -- i) push(p >> i);return data[p];}// O(log(n))U query_action(int p){static_assert(!HAS_QUERY && HAS_UPDATE);ASSERT(0 <= p && p < n);p += size;ifU for(auto i = log; i >= 1; -- i) push(p >> i);return data_action[p];}// O(log(n))T query(int ql, int qr){static_assert(HAS_QUERY);ASSERT(0 <= ql && ql <= qr && qr <= n);if(ql == qr) return T_id;ql += size, qr += size;ifU for(auto i = log; i >= 1; -- i){if(ql >> i << i != ql) push(ql >> i);if(qr >> i << i != qr) push(qr >> i);}T res_left = T_id, res_right = T_id;for(; ql < qr; ql >>= 1, qr >>= 1){if(ql & 1) res_left = TT(res_left, data[ql ++]);if(qr & 1) res_right = TT(data[-- qr], res_right);}return TT(res_left, res_right);}// O(1)T query_all() const{static_assert(HAS_QUERY);return data[1];}// O(n)vector<T> to_array(){static_assert(HAS_QUERY);ifU for(auto u = 1; u < size; ++ u) push(u);return vector<T>(data.begin() + size, data.begin() + size + n);}// O(n)vector<U> to_array_of_updates(){static_assert(!HAS_QUERY && HAS_UPDATE);for(auto u = 1; u < size; ++ u) push(u);return vector<U>(data_action.begin() + size, data_action.begin() + size + n);}// O(log(n))void set(int p, T x){static_assert(HAS_QUERY);ASSERT(0 <= p && p < n);p += size;ifU for(auto i = log; i >= 1; -- i) push(p >> i);data[p] = x;for(auto i = 1; i <= log; ++ i) refresh(p >> i);}// O(log(n))void set_action(int p, U f){static_assert(!HAS_QUERY && HAS_UPDATE);ASSERT(0 <= p && p < n);p += size;for(auto i = log; i >= 1; -- i) push(p >> i);data_action[p] = f;}// O(log(n))void update(int p, U f){static_assert(HAS_UPDATE);ASSERT(0 <= p && p < n);p += size;for(auto i = log; i >= 1; -- i) push(p >> i);ifQ{data[p] = UT(f, data[p]);for(auto i = 1; i <= log; ++ i) refresh(p >> i);}else data_action[p] = UU(f, data_action[p]);}// O(log(n))void update(int ql, int qr, U f){static_assert(HAS_UPDATE);ASSERT(0 <= ql && ql <= qr && qr <= n);if(ql == qr) return;ql += size, qr += size;for(auto i = log; i >= 1; -- i){if(ql >> i << i != ql) push(ql >> i);if(qr >> i << i != qr) push(qr >> i);}int _ql = ql, _qr = qr;for(; ql < qr; ql >>= 1, qr >>= 1){if(ql & 1) apply(ql ++, f);if(qr & 1) apply(-- qr, f);}ql = _ql, qr = _qr;ifQ for(auto i = 1; i <= log; ++ i){if(ql >> i << i != ql) refresh(ql >> i);if(qr >> i << i != qr) refresh(qr >> i);}}void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){static_assert(HAS_QUERY && HAS_UPDATE);ASSERT(0 <= ql && ql <= qr && qr <= n);if(ql == qr) return;ql += size, qr += size;for(auto i = log; i >= 1; -- i){if(ql >> i << i != ql) push(ql >> i);if(qr >> i << i != qr) push(qr >> i);}auto recurse = [&](auto self, int u)->void{if(exit_rule(data[u])) return;if(enter_rule(data[u])){apply(u, update_rule(data[u]));return;}push(u);self(self, u << 1), self(self, u << 1 | 1);refresh(u);};int _ql = ql, _qr = qr;for(; ql < qr; ql >>= 1, qr >>= 1){if(ql & 1) recurse(recurse, ql ++);if(qr & 1) recurse(recurse, -- qr);}ql = _ql, qr = _qr;for(auto i = 1; i <= log; ++ i){if(ql >> i << i != ql) refresh(ql >> i);if(qr >> i << i != qr) refresh(qr >> i);}}// pred(sum[ql, r)) is T, T, ..., T, F, F, ..., F// Returns max r with T// O(log(n))int max_pref(int ql, auto pred){static_assert(HAS_QUERY);ASSERT(0 <= ql && ql <= n && pred(T_id));if(ql == n) return n;ql += size;ifU for(auto i = log; i >= 1; -- i) push(ql >> i);T sum = T_id;do{while(~ql & 1) ql >>= 1;if(!pred(TT(sum, data[ql]))){while(ql < size){ifU push(ql);ql = ql << 1;if(pred(TT(sum, data[ql]))) sum = TT(sum, data[ql ++]);}return ql - size;}sum = TT(sum, data[ql]);++ ql;}while((ql & -ql) != ql);return n;}// pred(sum[l, qr)) is F, F, ..., F, T, T, ..., T// Returns min l with T// O(log(n))int min_suff(int qr, auto pred){static_assert(HAS_QUERY);ASSERT(0 <= qr && qr <= n && pred(T_id));if(qr == 0) return 0;qr += size;ifU for(auto i = log; i >= 1; -- i) push(qr - 1 >> i);T sum = T_id;do{-- qr;while(qr > 1 && qr & 1) qr >>= 1;if(!pred(TT(data[qr], sum))){while(qr < size){ifU push(qr);qr = qr << 1 | 1;if(pred(TT(data[qr], sum))) sum = TT(data[qr --], sum);}return qr + 1 - size;}sum = TT(data[qr], sum);}while((qr & -qr) != qr);return 0;}template<class output_stream>friend output_stream &operator<<(output_stream &out, segment_tree_base<HAS_QUERY, HAS_UPDATE, T, U, F1, F2, F3> seg){out << "{";for(auto i = 0; i < seg.n; ++ i){ifQ out << seg.query(i);else out << seg.query_action(i);if(i != seg.n - 1) out << ", ";}return out << '}';}#undef ASSERT#undef ifQ#undef ifU};// Supports querytemplate<class T, class F>auto make_Q_segment_tree(F TT, T T_id){using U = int;auto _UU = [&](U, U)->U{ return U{}; };auto _UT = [&](U, T)->T{ return T{}; };return segment_tree_base<true, false, T, U, F, decltype(_UU), decltype(_UT)>(TT, T_id, _UU, U{}, _UT);}// Supports updatetemplate<class U, class F>auto make_U_segment_tree(F UU, U U_id){using T = int;auto _TT = [&](T, T)->T{ return T{}; };auto _UT = [&](U, T)->T{ return T{}; };return segment_tree_base<false, true, T, U, decltype(_TT), F, decltype(_UT)>(_TT, T{}, UU, U_id, _UT);}// Supports query and updatetemplate<class T, class U, class F1, class F2, class F3>auto make_QU_segment_tree(F1 TT, T T_id, F2 UU, U U_id, F3 UT){return segment_tree_base<true, true, T, U, F1, F2, F3>(TT, T_id, UU, U_id, UT);}int main(){cin.tie(0)->sync_with_stdio(0);cin.exceptions(ios::badbit | ios::failbit);int h, w;cin >> h >> w;vector<string> a(h);copy_n(istream_iterator<string>(cin), h, a.begin());const int inf = 1e9;vector<vector<int>> dp(h, vector<int>(w, inf));for(auto j = 0; j < w; ++ j){if(a[h - 1][j] == '.'){dp[h - 1][j] = 0;}}auto seg = make_U_segment_tree([&](int x, int y){ return min(x, y); }, inf);for(auto i = h - 2; i >= 0; -- i){static vector<int> left(w), right(w);for(auto j = 0; j < w; ++ j){if(a[i][j] == '#'){left[j] = j;}else{left[j] = j > 0 ? left[j - 1] : -1;}}for(auto j = w - 1; j >= 0; -- j){if(a[i][j] == '#'){right[j] = j;}else{right[j] = j < w - 1 ? right[j + 1] : w;}}seg.build_action(w);for(auto j = 0; j < w; ++ j){if(a[i][j] == '#'){continue;}int l = max(j - dp[i + 1][j], left[j] + 1);int r = min(j + dp[i + 1][j] + 1, right[j]);seg.update(l, r, dp[i + 1][j]);}dp[i] = seg.to_array_of_updates();for(auto j = 0; j < w; ++ j){if(a[i][j] == '#'){dp[i][j] = inf;}}for(auto j = 1; j < w; ++ j){if(a[i][j] == '.' && dp[i][j - 1] + 1 < dp[i][j]){dp[i][j] = dp[i][j - 1] + 1;}}for(auto j = w - 2; j >= 0; -- j){if(a[i][j] == '.' && dp[i][j + 1] + 1 < dp[i][j]){dp[i][j] = dp[i][j + 1] + 1;}}}ranges::copy(dp[0], ostream_iterator<int>(cout, "\n"));return 0;}/**/