結果
問題 | No.2657 Falling Block Game |
ユーザー |
![]() |
提出日時 | 2024-03-02 01:31:51 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 33,970 bytes |
コンパイル時間 | 4,315 ms |
コンパイル使用メモリ | 252,044 KB |
実行使用メモリ | 15,752 KB |
最終ジャッジ日時 | 2024-09-29 15:45:02 |
合計ジャッジ時間 | 7,477 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | AC * 2 WA * 35 |
ソースコード
#include <algorithm>#include <bit>#include <bitset>#include <cassert>#include <complex>#include <climits>#include <cstdio>#include <cstdlib>#include <cmath>#include <deque>#include <iostream>#include <map>#include <iomanip>#include <optional>#include <random>#include <ranges>#include <unordered_set>#include <unordered_map>#include <vector>#include <set>#include <string>#include <type_traits>#include <variant>using std::__gcd;using std::bitset;using std::cin;using std::cerr;using std::complex;using std::cout;using std::deque;using std::endl;using std::greater;using std::hash;using std::istream;using std::min;using std::map;using std::max;using std::multiset;using std::nullopt;using std::optional;using std::ostream;using std::pair;using std::rotate;using std::set;using std::setprecision;using std::string;using std::string_view;using std::swap;using std::tie;using std::to_string;using std::tuple;using std::unordered_map;using std::unordered_set;using std::vector;#if __cplusplus >= 201709Lusing std::ranges::sort;using std::ranges::views::iota;using std::views::reverse;using std::views::filter;using std::views::transform;#endif#define L(expr) ([&](const auto& _) { return (expr) ; })#define Map(expr) (transform((L((expr)))))#define Filter(expr) (filter((L((expr)))))template <typename T>ostream& operator<< (ostream& o, const multiset<T>& v) {for (const auto& x : v) o << x << " ";return o;}template <typename T>ostream& operator<< (ostream& o, const unordered_set<T>& v) {o << "{";for (const auto& x : v) o << x << " ";o << "}";return o;}template<typename T, typename U>ostream& operator<< (ostream& o, const pair<T, U>& p) {o << "<" << p.first << ", " << p.second << ">";return o;}template <typename T>ostream& operator<< (ostream& o, const vector<T>& v) {for (const auto& x : v) o << x << " ";return o;}template <typename T>ostream& operator<< (ostream& o, const set<T>& v) {for (const auto& x : v) o << x << " ";return o;}template <typename T>ostream& operator<< (ostream& o, const deque<T>& v) {for (const auto& x : v) o << x << " ";return o;}template <typename K, typename V>ostream& operator<<(ostream& o, const unordered_map<K, V>& m) {o << "{";for (const auto& [k, v] : m)o << " " << k << ": " << v << ",";o << "}";return o;}template <typename K, typename V>ostream& operator<<(ostream& o, const map<K, V>& m) {o << "{";for (const auto& [k, v] : m)o << " " << k << ": " << v << ",";o << "}";return o;}template <typename T>ostream& operator<< (ostream& o, const vector<vector<T>>& v) {for (const auto& x : v) o << x << endl;return o;}ostream& operator<< (ostream& o, const vector<string>& v) {for (const auto& x : v) o << x << endl;return o;}void print_to(ostream& o) {o << endl;};template <typename T, typename... A>void print_to(ostream& o, const T& t, const A&... a) {o << t << " ";print_to(o, a...);}template <typename... A>void out(const A&... a) {print_to(cout, a...);}template <typename T, typename... A>const T& cerr_and_return(const T& t, const A&... a) {print_to(cerr, "\t", t, " ← ", a...);return t;}template <typename T, typename... A>T& cerr_and_return(T& t, const A&... a) {print_to(cerr, "\t", t, " ← ", a...);return t;}#ifdef DEBUG#define err(...) print_to(cerr, "\t[", #__VA_ARGS__, "]", " = ", __VA_ARGS__)#else#define err(...)#endif#ifdef DEBUG#define E(expr) (cerr_and_return((expr), (#expr)))#else#define E(expr) (expr)#endifclass in {public:in() {}in(istream &i) : i(i) {}in(int n) : n(n) {}template <typename T>operator T () {T n;i >> n;return n;}template <typename T>operator deque<T> () {deque<T> v(n ? n.value() : static_cast<int>(*this));for (auto& x : v) x = *this;return v;}template <typename T>operator multiset<T> () {return insert<multiset<T>>(n ? n.value() : static_cast<int>(*this));}template <typename T, typename U>operator pair<T, U> () {return {*this, *this};}template <typename T>operator complex<T> () {return {*this, *this};}template <typename T>operator set<T> () {return insert<set<T>>(n ? n.value() : static_cast<int>(*this));}template <typename T>operator vector<T> () {vector<T> v(n ? n.value() : static_cast<int>(*this));for (auto& x : v) x = static_cast<T>(*this);return v;}private:template <typename S>S insert(int n) {S s;while (n--) s.insert(static_cast<typename S::key_type>(*this));return s;}optional<int> n;istream& i = cin;} _;/*template <typename T>istream& operator>> (istream& i, T& t) {t = static_cast<T>(in(i));return i;}*/// Test for complex integers modulo: pair<Mod<>, Mod<>>// https://yukicoder.me/problems/no/2651template <typename T>using Complex = pair<T, T>;template <typename U, typename V>pair<U, V> operator += (pair<U, V>& p, const pair<U, V>& q) {p.first += q.first;p.second += q.second;return p;}template <typename U, typename V>pair<U, V> operator + (pair<U, V> p, const pair<U, V>& q) {return p += q;}template <typename U, typename V>pair<U, V> operator -= (pair<U, V>& p, const pair<U, V>& q) {p.first -= q.first;p.second -= q.second;return p;}template <typename U, typename V>pair<U, V> operator - (pair<U, V> p, const pair<U, V>& q) {return p -= q;}template <typename U, typename V>pair<U, V> operator * (pair<U, V> p, const pair<U, V>& q) {return p *= q;}template <typename U, typename V, typename W>pair<U, V> operator * (pair<U, V> p, const W& q) {return p *= q;}template <typename U, typename V, typename W>pair<U, V> operator * (const W& q, pair<U, V> p) {return {q * p.first, q * p.second};}template <typename U, typename V>pair<U, V> operator *= (pair<U, V>& p, const pair<U, V>& q) {U new_first = p.first * q.first - p.second * q.second;V new_second = p.first * q.second + p.second * q.first;p.first = new_first;p.second = new_second;return p;}template <typename U, typename V, typename W>pair<U, V> operator *= (pair<U, V>& p, const W& q) {p.first *= q;p.second *= q;return p;}template <typename U, typename V>pair<U, V> operator / (pair<U, V> p, const pair<U, V>& q) {err("pair", p, "/", "pair", q);return p /= q;}template <typename U, typename V, typename W>pair<U, V> operator / (pair<U, V> p, const W& q) {err("pair", p, "/", "scalar", q);return p /= q;}template <typename U, typename V, typename W>pair<U, V> operator / (const W& q, pair<U, V> p) {return pair<U, V>{q, 0} / p;}template <typename S, typename T>complex<T> operator / (const S& s, complex<T> c) {return complex<T>{s, 0} / c;}template <typename U, typename V, typename W, typename X>pair<U, V> operator /= (pair<U, V>& p, const pair<W, X>& q) {err("pair", p, "/=", "pair", q);pair<W, X> c = {q.first, -q.second};p *= c;auto m2 = q * c;assert(m2.second == 0);p /= m2.first;return p;}template <typename U, typename V, typename W>pair<U, V> operator /= (pair<U, V>& p, const W& q) {err("pair", p, "/=", "scalar", q);p.first /= q;p.second /= q;return p;}template <typename U, typename V>double hypot(const pair<U, V>& p) {return hypot(1.0 * p.first, 1.0 * p.second);}template <typename U, typename V>pair<U, V> conj(const pair<U, V>& p) {return {p.first, -p.second};}template <typename U, typename V>struct std::hash<pair<U, V>> {std::size_t operator () (const pair<U, V>& p) const {return hash<U>{}(p.first) ^ (hash<V>{}(p.second) << 1); // https://en.cppreference.com/w/cpp/utility/hash}};template <typename Element, typename... List>struct Contains {static constexpr bool value = false;};template <typename Element, typename... List>struct Contains<Element, Element, List...> {static constexpr bool value = true;};template <typename Element, typename Other, typename... List>struct Contains<Element, Other, List...> {static constexpr bool value = Contains<Element, List...>::value;};template <typename... Args>inline constexpr bool contains_v = Contains<Args...>::value;struct Empty {};#define TREE_SUM#define TREE_MULTIPLYtemplate <typename V = long long>struct FastTree {using K = long long;const K a = -1e18, b = 1e18;struct Node {Node *left = nullptr, *right = nullptr;V value = 0;#ifdef TREE_SUMV sum_ = 0;#endif#ifdef TREE_MULTIPLYV multiplier = 1;#endifdeque<string> to_lines(K a, K b) const {const K m = a + (b - a + 1) / 2 - 1;deque<string> lines = left ? left->to_lines(a, m) : deque<string>{};if (right) {deque<string> right_lines = right->to_lines(m + 1, b);size_t pad = 0;for (string_view l : lines) pad = max(pad, l.size());for (string& l : lines) l += string(pad - l.size(), ' ') + ']';while (lines.size() < right_lines.size())lines.push_back(string(pad + !!pad, ' '));for (int i = 0; i < right_lines.size(); ++i)lines[i] += right_lines[i];}lines.push_front("[" + to_string(a) + " " + to_string(b));if (value != 0) lines[0] += (value >= 0 ? " +" : " ") + to_string(value);#ifdef TREE_MULTIPLYif (multiplier != 1) lines[0] += " *" + to_string(multiplier);#endif#ifdef TREE_SUMlines[0] += " s=" + to_string(sum_);#endifreturn lines;}} root;V operator[] (const K k) const {if (k < a || b < k) return 0;K a = this->a, b = this->b, m;const Node* node = &root;V r = 0;while (node) {r += node->value;m = a + (b - a + 1) / 2 - 1;if (k <= m) {b = m;node = node->left;} else {a = m + 1;node = node->right;}}return r;}#ifdef TREE_SUMV sum(const K l, const K r) const {static vector<tuple<K, K, const Node*#ifdef TREE_MULTIPLY, V#endif>> stack(128);int top = 0;stack[top] = {a, b, &root#ifdef TREE_MULTIPLY, 1#endif};K a, b, m;const Node* node;#ifdef TREE_MULTIPLYV multiplier;#endifV s = 0;while (top >= 0) {tie(a, b, node#ifdef TREE_MULTIPLY, multiplier#endif) = stack[top--];if (l <= a && b <= r) s +=#ifdef TREE_MULTIPLYmultiplier *#endifnode->sum_;else {s += max(static_cast<K>(0), 1 + min(r, b) - max(l, a)) * node->value#ifdef TREE_MULTIPLY* multiplier#endif;m = a + (b - a + 1) / 2 - 1;if (l <= m && a <= r && node->left) stack[++top] = {a, m, node->left#ifdef TREE_MULTIPLY, multiplier * node->multiplier#endif};if (l <= b && m <= r && node->right) stack[++top] = {m + 1, b, node->right#ifdef TREE_MULTIPLY, multiplier * node->multiplier#endif};}}return s;}#endifvoid add(const K l, const K r, V v) {static vector<tuple<K, K, Node*, char>> stack(128);int top = 0;stack[top] = {a, b, &root, 0};K a, b, m;Node* node;bool visited;while (top >= 0) {tie(a, b, node, visited) = stack[top];//err(a, b, node, top, l, r);if (visited) {--top;#ifdef TREE_MULTIPLYif (!(b < l || r < a) && !(l <= a && b <= r)) v *= node->multiplier;#endif//err("exiting", a, b, node->value);node->sum_ = node->value * (b - a + 1);if (node->left) node->sum_ += node->left->sum_#ifdef TREE_MULTIPLY* node->multiplier#endif;if (node->right) node->sum_ += node->right->sum_#ifdef TREE_MULTIPLY* node->multiplier#endif;} else {//err("entering", a, b);std::get<3>(stack[top]) = true;if (b < l || r < a);else if (l <= a && b <= r) { node->value += v; }else {#ifdef TREE_MULTIPLYv /= node->multiplier;#endifm = a + (b - a + 1) / 2 - 1;if (l <= m) {if (!node->left) node->left = new Node;stack[++top] = {a, m, node->left, false};}if (m < r) {if (!node->right) node->right = new Node;stack[++top] = {m + 1, b, node->right, false};}}}}}#ifdef TREE_MULTIPLYvoid multiply(const K l, const K r, const V v) {static vector<tuple<K, K, Node*, bool>> stack(128);int top = 0;stack[top] = {a, b, &root, false};K a, b, m;Node* node;bool visited;while (top >= 0) {tie(a, b, node, visited) = stack[top];//err(a, b, node, top, l, r);if (visited) {--top;//err("exiting", a, b, node->value);node->sum_ = node->value * (b - a + 1);if (node->left) node->sum_ += node->left->sum_#ifdef TREE_MULTIPLY* node->multiplier#endif;if (node->right) node->sum_ += node->right->sum_#ifdef TREE_MULTIPLY* node->multiplier#endif;} else {//err("entering", a, b);std::get<3>(stack[top]) = true;if (b < l || r < a);else if (l <= a && b <= r) {node->value *= v;node->multiplier *= v;}else {m = a + (b - a + 1) / 2 - 1;if (l <= m) {if (!node->left) node->left = new Node;stack[++top] = {a, m, node->left, false};}if (m < r) {if (!node->right) node->right = new Node;stack[++top] = {m + 1, b, node->right, false};}}}}}#endiffriend ostream& operator << (ostream& o, const FastTree& t) {deque<string> lines = t.root.to_lines(t.a, t.b);size_t pad = 0;for (string_view l : lines) pad = max(pad, l.size());for (string& l : lines) l += string(pad - l.size(), ' ') + ']';for (string_view l : lines) o << l << endl;return o;}};struct Sum {};template <typename V = long long>struct Tree {const long long a, b;using Interval = pair<long long, long long>;inline static pair<Interval, Interval> split(const Interval& i) {auto [l, r] = i;long long m = l + (r - l + 1) / 2 - 1;return {{l, m}, {m + 1, r}};}inline static bool in(const Interval& i, const Interval& j) {return j.first <= i.first && i.second <= j.second;}inline static bool disjoint(const Interval& i, const Interval& j) {return i.second < j.first || j.second < i.first;}inline static bool intersect(const Interval& i, const Interval& j) {return !disjoint(i, j);}struct Node {#ifdef TREE_MULTIPLYV subtree_multiplier = 1;#endifV value = 0 /*,, min_ = 0, max_ = 0 */;V sum_ = 0;Node *left = nullptr, *right = nullptr;~Node() {if (left) delete left;if (right) delete right;}template <typename T>void set(const Interval& ni, long long l, const vector<T>& v) {Interval vi = {l, l + v.size() - 1};if (disjoint(ni, vi)) return;assert(value == 0);#ifdef TREE_MULTIPLYassert(subtree_multiplier == 1);#endifif (ni.first == ni.second) {value = v[ni.first - l];} else {auto [li, ri] = split(ni);if (intersect(li, vi)) {if (!left) left = new Node;left->set(li, l, v);}if (intersect(ri, vi)) {if (!right) right = new Node;right->set(ri, l, v);}}update(ni);}void set(const Interval& ni, const Interval& vi, V v) {if (disjoint(ni, vi)) return;if (in(ni, vi)) {value = v;#ifdef TREE_MULTIPLYsubtree_multiplier = 1;#endifif (left) delete left; left = nullptr;if (right) delete right; right = nullptr;} else {v -= value;#ifdef TREE_MULTIPLYassert(subtree_multiplier != 0);v /= subtree_multiplier;#endifauto [li, ri] = split(ni);if (intersect(li, vi)) {if (!left) left = new Node;left->set(li, vi, v);}if (intersect(ri, vi)) {if (!right) right = new Node;right->set(ri, vi, v);}}update(ni);}void add(const Interval& ni, const Interval& vi, V v#ifdef TREE_MULTIPLY, V denominator#endif) {if (disjoint(ni, vi)) return;if (in(ni, vi)) {value += v#ifdef TREE_MULTIPLY/ denominator#endif;} else {auto [li, ri] = split(ni);if (intersect(li, vi)) {if (!left) left = new Node;left->add(li, vi, v#ifdef TREE_MULTIPLY, denominator * subtree_multiplier#endif);}if (intersect(ri, vi)) {if (!right) right = new Node;right->add(ri, vi, v#ifdef TREE_MULTIPLY, denominator * subtree_multiplier#endif);}}update(ni);}void multiply(const Interval& ni, const Interval& vi, V v) {if (disjoint(ni, vi)) return;if (v == 0) {set(ni, vi, 0);} else if (in(ni, vi)) {value *= v;subtree_multiplier *= v;} else {auto [li, ri] = split(ni);if (!left) left = new Node;if (!right) right = new Node;left->add(li, li, value, subtree_multiplier);right->add(ri, ri, value, subtree_multiplier);value = 0;left->multiply(li, vi, v);right->multiply(ri, vi, v);}update(ni);}void get(const Interval& ni, const Interval& qi, vector<V>& result,#ifdef TREE_MULTIPLYV multiplier = 1,#endifV addition = 0) {if (disjoint(ni, qi)) return;V v =#ifdef TREE_MULTIPLYmultiplier *#endifvalue + addition;if (ni.first == ni.second) {result.push_back(v);} else {const auto [li, ri] = split(ni);if (left) {left->get(li, qi, result,#ifdef TREE_MULTIPLYmultiplier * subtree_multiplier,#endifv);} else {for (long long i = std::max(li.first, qi.first);i <= std::min(li.second, qi.second); ++i)result.push_back(v);}if (right) {right->get(ri, qi, result,#ifdef TREE_MULTIPLYmultiplier * subtree_multiplier,#endifv);} else {for (long long i = std::max(ri.first, qi.first);i <= std::min(ri.second, qi.second); ++i)result.push_back(v);}}}V sum(const Interval& ni, const Interval& qi, bool cache=true) {if (disjoint(ni, qi)) return 0;if (in(ni, qi) && cache) return sum_;auto [li, ri] = split(ni);return value * (std::min(ni.second, qi.second) - std::max(ni.first, qi.first) + 1)+#ifdef TREE_MULTIPLYsubtree_multiplier *#endif((left ? left->sum(li, qi) : 0) +(right ? right->sum(ri, qi) : 0));}/*V min(const Interval& ni, const Interval& qi, bool cache=true) {assert(intersect(ni, qi));if (in(ni, qi) && cache) return min_;auto [li, ri] = split(ni);V kids = 0;if (intersect(li, qi) && intersect(ri, qi))kids = std::min(left ? left->min(li, qi) : 0, right ? right->min(ri, qi) : 0);else if (intersect(li, qi) && left)kids = left->min(li, qi);else if (intersect(ri, qi) && right)kids = right->min(ri, qi);return value + /*subtree_multiplier **/ /*kids;}*/// UNTESTED/*V max(const Interval& ni, const Interval& qi, bool cache=true) {assert(intersect(ni, qi));if (in(ni, qi) && cache) return max_;auto [li, ri] = split(ni);V kids = 0;if (intersect(li, qi) && intersect(ri, qi))kids = std::max(left ? left->max(li, qi) : 0, right ? right->max(ri, qi) : 0);else if (intersect(li, qi) && left)kids = left->max(li, qi);else if (intersect(ri, qi) && right)kids = right->max(ri, qi);return value + /*subtree_multiplier * kids;}*/void update(const Interval& i) {sum_ = sum(i, i, false);//max_ = max(i, i, false);//min_ = min(i, i, false);}/*void print() {if (left) left->print();if (value)//cout << "[" << a << ", " << b << "; len=" << b - a + 1 << "] " << value << " " << sum_ << endl;if (right) right->print();}*/} root;Tree(long long a = -1e18, long long b = 1e18): a(a), b(b) {}void add(long long l, long long r, V v) {root.add({a, b}, {l, r}, v#ifdef TREE_MULTIPLY, 1#endif);}#ifdef TREE_MULTIPLYvoid multiply(long long l, long long r, V v) {root.multiply({a, b}, {l, r}, v);}#endifvoid set(long long l, long long r, V v) {root.set({a, b}, {l, r}, v);}template <typename T>void set(long long l, const vector<T>& v) {root.set({a, b}, l, v);}vector<V> get(long long l, long long r) {vector<V> result;result.reserve(r - l + 1);root.get({a, b}, {l, r}, result);return result;}V sum(long long l, long long r) {return root.sum({a, b}, {l, r});}/*V max(long long l, long long r) {return root.max({a, b}, {l, r});}V min(long long l, long long r) {return root.min({a, b}, {l, r});}*/};auto read_undirected(int n, int m) {vector e(n + 1, vector<int>());while (m--) {int u = _, v = _;e[u].push_back(v);e[v].push_back(u);}return e;}struct GraphSearchResult {GraphSearchResult(int size): d(size, -1), p(size), v_to_cc(size, -1) {};vector<int> postorder, d, p, v_to_cc;vector<vector<int>> cc;};GraphSearchResult dfs(const vector<vector<int>>& edges) {GraphSearchResult r(edges.size());auto& [postorder, d, p, v_to_cc, cc] = r;vector<pair<int, int>> q;for (int s = 1; s < edges.size(); ++s) if (d[s] < 0) {cc.push_back({});q.push_back({0, s});while (q.size()) {auto [w, u] = q.back();q.pop_back();if (d[u] >= 0) continue;postorder.push_back(u);d[u] = d[w] + 1;p[u] = w;v_to_cc[u] = cc.size() - 1;cc.back().push_back(u);for (int v : edges[u]) q.push_back({u, v});}}std::reverse(postorder.begin(), postorder.end());return r;}vector<int> return_vertices(const vector<vector<int>>& edges, const GraphSearchResult& s) {vector<int> r(s.p.size(), -1);for (int u : s.postorder) {r[u] = u;int b = s.d[u];for (int v : edges[u]) if (v != s.p[u]) {int c = s.p[v] == u ? r[v] : v;if (s.d[c] < b) { b = s.d[c], r[u] = c; }}}return r;}struct GcdResult {long long g;long long x;long long y;};GcdResult extended_gcd(const long long aa, const long long bb) {assert(aa || bb);long long a = abs(aa), b = abs(bb);bool swapped = b > a;if (swapped) swap(a, b);static vector<long long> k(512);int i = 0;while (b) {k[i++] = a / b;a %= b;swap(a, b);}assert(i <= 512);long long x = 1, y = 0;while (i) {swap(x, y);y -= x * k[--i];}if (swapped) swap(x, y);return {a, aa < 0 ? -x : x, bb < 0 ? -y : y};}long long inv(long long a, long long m) {GcdResult r = extended_gcd(a, m);assert(r.g == 1);long long result = (r.x % m + m) % m;assert(0 <= result);assert(result < m);return result;}long long lcm(long long a, long long b) {return (a / std::gcd(a, b)) * b;}inline long long power(long long a, long long b, long long m) {long long r = 1;for (long long i = 0, e = (a % m); (1 << i) <= b; ++i, e = (e * e) % m)if (b & (1 << i)) r = (r * e) % m;return r;}struct Operators {/*inline friend auto operator -= (auto& f, const auto& g) {return f += -g;}inline friend auto operator /= (auto& f, const auto& g) {return f *= g.inv();}*/};struct Fraction : Operators {inline friend Fraction operator -= (Fraction& f, const Fraction& g) {return f += -g;}inline friend Fraction operator /= (Fraction& f, const Fraction& g) {return f *= g.inv();}friend Fraction operator + (Fraction f, const Fraction& g) {return f += g;}friend Fraction operator - (Fraction f, const Fraction& g) {return f -= g;}friend Fraction operator * (Fraction f, const Fraction& g) {return f *= g;}friend Fraction operator / (Fraction f, const Fraction& g) {return f /= g;}friend bool operator == (const Fraction& f, const Fraction& g) {long long l = lcm(f.denominator, g.denominator);return f.numerator * (l / f.denominator) == g.numerator * (l / g.denominator);}friend bool operator < (const Fraction& f, const Fraction& g) {long long l = lcm(f.denominator, g.denominator);return f.numerator * (l / f.denominator) < g.numerator * (l / g.denominator);}long long numerator = 0, denominator = 1;Fraction() {}Fraction(long long n) : numerator(n) {}Fraction(long long n, long long d) : numerator(n), denominator(d) {simplify();}Fraction operator += (const Fraction& f) {long long l = lcm(denominator, f.denominator);numerator = numerator * (l / denominator) + f.numerator * (l / f.denominator);denominator = l;simplify();return *this;}Fraction operator - () const {return {-numerator, denominator};}Fraction operator *= (const Fraction& f) {long long g1 = __gcd(numerator, f.denominator),n1 = numerator / g1,d1 = f.denominator / g1,g2 = __gcd(denominator, f.numerator),n2 = f.numerator / g2,d2 = denominator / g2;numerator = n1 * n2;denominator = d1 * d2;simplify();return *this;}Fraction inv() const {return {denominator, numerator};}void simplify() {long long g = __gcd(numerator, denominator);numerator /= g;denominator /= g;if (denominator < 0) {numerator = -numerator;denominator = -denominator;}}friend ostream& operator << (ostream& o, const Fraction& f) {o << f.numerator << "/" << f.denominator ;return o;}};template <long long M=998244353>struct Mod {inline Mod<M> operator -= (Mod<M> g) {return value = (value + M - g.value) % M;}inline Mod<M> operator /= (Mod<M> g) {return value = (value * ::inv(g.value, M)) % M;}inline friend Mod<M> operator + (Mod<M> f, Mod<M> g) {return f += g;}inline friend Mod<M> operator - (Mod<M> f, Mod<M> g) {return f -= g;}inline friend Mod<M> operator * (Mod<M> f, Mod<M> g) {return f *= g;}inline friend Mod<M> operator / (Mod<M> f, Mod<M> g) {return f /= g;}inline friend bool operator == (Mod<M> f, Mod<M> g) {return f.value == g.value;}inline friend bool operator < (Mod<M> f, Mod<M> g) {return f.value < g.value;}long long value;inline Mod(long long v = 0) : value((M + v % M) % M) {}inline Mod<M> operator += (Mod<M> b) {value = (value + b.value) % M;return *this;}inline Mod<M> operator - () const {return M - value;}inline Mod<M> operator *= (Mod<M> b) {value = (value * b.value) % M;return *this;}inline Mod<M> inv() const {return ::inv(value, M);}inline friend ostream& operator << (ostream& o, Mod<M> a) {o << a.value;return o;}inline friend istream& operator >> (istream& i, Mod<M>& a) {return i >> a.value;}};map<long long, long long> factorize(long long n) {map<long long, long long> r;for (long long i = 2; i * i <= n; ++i)for (; n % i == 0; n /= i)++r[i];if (n > 1) ++r[n];return r;}template<typename T, typename U>auto cdiv(T t, U u) {return (t + u - 1) / u;}inline vector<int> subsets(int s) {vector<int> change;for (int t = s, b = 1 << __builtin_ctz(t) ; t; t ^= b, b = 1 << __builtin_ctz(t))change.push_back(b - (s & (b - 1)));vector<int> r = {0};int over = 1 << __builtin_popcount(s);for (int t = 1, st = 0; t < over; ++t)r.push_back(st += change[__builtin_ctz(t)]);return r;}const vector<pair<int, int>> four_directions {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};template <typename V>bool is_index(const vector<V>& v, int i, int j) {return 0 <= i && i < v.size() && 0 <= j && j < v[i].size();}template <typename V>bool is_index(const vector<V>& v, pair<int, int> ij) {return is_index(v, ij.first, ij.second);}auto indices(const vector<string>& v) {vector<pair<int, int>> r;for (int i = 0; i < v.size(); ++i)for (int j = 0; j < v[i].size(); ++j)r.push_back({i, j});return r;}auto four_neighbors(const vector<string>& b, pair<int, int> i) {vector<pair<int, int>> r;for (auto d : four_directions)if (is_index(b, i + d))r.push_back(i + d);return r;}vector<string> get_rotated_clockwise(const vector<string>& t) {vector<string> r(t[0].size(), string(t.size(), ' '));for (int i = 0; i < t.size(); ++i)for (int j = 0; j < t[0].size(); ++j)r[j][t.size() - i - 1] = t[i][j];return r;}template <typename T>long long sum(const T& t) {return std::accumulate(begin(t), end(t), 0ll);}vector<long long> get_partial_sums(const vector<long long>& v) {vector<long long> p {0};partial_sum(v.cbegin(), v.cend(), back_inserter(p));return p;}void Yes(bool b) {out(b ? "Yes" : "No");}// Wczytać wektor i inne kolekcje stringówvoid testTreeParity() {{const long long M = 2000000000;Tree t(-M, M);FastTree<long long> f{-M, M};for (long long i = 0; ; ++i) {if (i % 100000 == 0) out(i);{long long a = rand() % M, b = rand() % M, v = rand() % M;if (a > b) swap(a, b);err("add", a, b, v);t.add(a, b, v);f.add(a, b, v);}{//cerr << f;long long k = rand() % M;long long tr = t.get(k, k)[0], fr = f[k];err("get", k, tr, fr);assert(tr == fr);}#ifdef TREE_SUM{long long a = rand() % M, b = rand() % M;if (a > b) swap(a, b);long long tr = t.sum(a, b), fr = f.sum(a, b);if (tr != fr) {cerr << f;out("sum", a, b, tr, fr);}assert(tr == fr);}#endif#ifdef TREE_MULTIPLY{long long a = rand() % M, b = rand() % M, v = rand() % M;if (a > b) swap(a, b);err("multiply", a, b, v);t.multiply(a, b, v);f.multiply(a, b, v);}#endif}}}void testTreeSpeed() {{const int M = 2000000000;//Tree<long long> t;FastTree<long long> t;for (long long i = 0; i < 500000; ++i) {if (i % 100000 == 0) err(i);{long long a = rand() % M, b = rand() % M, v = rand() % M;if (a > b) swap(a, b);//err("add", a, b, v);t.add(a, b, v);}{//cerr << f;//long long k = rand() % M;//long long tr = t.sum(k, k);//t.get(k, k)[0];//long long fr = t[k];}{long long a = rand() % M, b = rand() % M;if (a > b) swap(a, b);t.sum(a, b);}}}}int main() {std::ios::sync_with_stdio(false);cout << setprecision(50);cerr << setprecision(50);int h = _, w = _;vector<string> g = in(h);const int inf = 1e9 + 7;vector d(h, vector<int>(w, inf));d[0] = vector<int>(w, 0);for (int i = 1; i < h; ++i) {err(i);multiset<int> left, mid, right;int pi = 0;vector<tuple<int, int, int, bool>> p;for (int k = 0; k < w; ++k) {err(k);if (g[h - 1 - i][k] == '.') {if (k == 0 || g[h - 1 - i][k - 1] == '#') {p.clear();for (int j = k; j < w && g[h - 1 - i][j] == '.'; ++j) if (int c = d[i - 1][j]; c < inf) {left.insert(j);p.emplace_back(j - c, j, c, true);p.emplace_back(j + c + 1, j, c, false);}std::sort(p.begin(), p.end());err("sorted");pi = 0;}for (; pi < p.size() && std::get<0>(p[pi]) <= k; ++pi) {auto [jc, j, c, f] = p[pi];err(jc, j, c, f);if (f) {left.erase(left.find(j));mid.insert(c);} else {mid.erase(mid.find(c));right.insert(j);}}err("moved");d[i][k] = inf;if (left.size()) d[i][k] = min( d[i][k], *left.begin() - k);if (mid.size()) d[i][k] = min( d[i][k], *mid.begin());if (right.size()) d[i][k] = min( d[i][k], k - *--right.end());} else {left.clear();mid.clear();right.clear();}}}out(d.back());err(g);err(d);return 0;}