結果
| 問題 | No.2657 Falling Block Game |
| ユーザー |
 as277575
|
| 提出日時 | 2024-03-02 01:59:30 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 35,241 bytes |
| コンパイル時間 | 3,569 ms |
| コンパイル使用メモリ | 213,856 KB |
| 実行使用メモリ | 17,552 KB |
| 最終ジャッジ日時 | 2024-09-29 15:45:42 |
| 合計ジャッジ時間 | 9,002 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | AC | 2 ms
6,816 KB |
| testcase_04 | AC | 55 ms
17,264 KB |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
ソースコード
#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 >= 201709L
using 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)
#endif
class 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/2651
template <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_MULTIPLY
template <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_SUM
V sum_ = 0;
#endif
#ifdef TREE_MULTIPLY
V multiplier = 1;
#endif
deque<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_MULTIPLY
if (multiplier != 1) lines[0] += " *" + to_string(multiplier);
#endif
#ifdef TREE_SUM
lines[0] += " s=" + to_string(sum_);
#endif
return 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_SUM
V 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_MULTIPLY
V multiplier;
#endif
V s = 0;
while (top >= 0) {
tie(a, b, node
#ifdef TREE_MULTIPLY
, multiplier
#endif
) = stack[top--];
if (l <= a && b <= r) s +=
#ifdef TREE_MULTIPLY
multiplier *
#endif
node->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;
}
#endif
void 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_MULTIPLY
if (!(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_MULTIPLY
v /= node->multiplier;
#endif
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};
}
}
}
}
}
#ifdef TREE_MULTIPLY
void 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};
}
}
}
}
}
#endif
friend 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_MULTIPLY
V subtree_multiplier = 1;
#endif
V 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_MULTIPLY
assert(subtree_multiplier == 1);
#endif
if (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_MULTIPLY
subtree_multiplier = 1;
#endif
if (left) delete left; left = nullptr;
if (right) delete right; right = nullptr;
} else {
v -= value;
#ifdef TREE_MULTIPLY
assert(subtree_multiplier != 0);
v /= subtree_multiplier;
#endif
auto [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_MULTIPLY
V multiplier = 1,
#endif
V addition = 0) {
if (disjoint(ni, qi)) return;
V v =
#ifdef TREE_MULTIPLY
multiplier *
#endif
value + 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_MULTIPLY
multiplier * subtree_multiplier,
#endif
v);
} 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_MULTIPLY
multiplier * subtree_multiplier,
#endif
v);
} 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_MULTIPLY
subtree_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_MULTIPLY
void multiply(long long l, long long r, V v) {
root.multiply({a, b}, {l, r}, v);
}
#endif
void 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ów
void 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);
}
}
}
}
vector<string> gen(int h, int w) {
vector<string> g(h, string(w, '.'));
for (int i = 1; i < h - 1; ++i)
for (int j = 0; j < w; ++j)
g[i][j] = rand() % 2 ? '.' : '#';
return g;
}
vector<vector<int>> brut(const vector<string>& g) {
const int inf = 1e9 + 7, h = g.size(), w = g[0].size();
vector d(h, vector<int>(w, inf));
d[0] = vector<int>(w, 0);
for (int i = 1; i < h; ++i) {
for (int j = 0; j < w; ++j) {
for (int k = j; k >= 0 && g[h - 1 - i][k] == '.'; --k)
d[i][j] = min(d[i][j], max(abs(k - j), d[i - 1][k]));
for (int k = j; k < w && g[h - 1 - i][k] == '.'; ++k)
d[i][j] = min(d[i][j], max(abs(k - j), d[i - 1][k]));
}
}
return d;
}
vector<vector<int>> solve(const vector<string>& g) {
const int inf = 1e9 + 7, h = g.size(), w = g[0].size();
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();
}
}
}
return d;
}
int main() {
std::ios::sync_with_stdio(false);
cout << setprecision(50);
cerr << setprecision(50);
/*
for (int h = 3; h < 10; ++h)
for (int w = 1; w < 10; ++w) {
out(h, w);
for (int iter = 0; iter < 100000; ++iter) {
auto g = gen(h, w);
auto rs = solve(g), rb = brut(g);
if (iter % 100000 == 0 || rs != rb) {
out(g);
out("rs");
out(rs);
out("rb");
out(rb);
Yes(rs == rb);
}
assert(rs == rb);
}
}
return 0;
*/
int h = _, w = _;
vector<string> g = in(h);
auto r = solve(g), rb = solve(g);
out(rb.back());
return 0;
}