結果

問題 No.2657 Falling Block Game
コンテスト
ユーザー hamath
提出日時 2024-03-01 23:33:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 597 ms / 2,000 ms
コード長 10,245 bytes
コンパイル時間 3,143 ms
コンパイル使用メモリ 241,040 KB
最終ジャッジ日時 2025-02-19 23:16:44
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef LOCAL
//#define _GLIBCXX_DEBUG
#else
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl")
#endif

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<char> Vc;
typedef vector<P> VP;
typedef vector<VP> VVP;
typedef vector<Vec> VV;
typedef vector<Vi> VVi;
typedef vector<Vc> VVc;
typedef vector<VV> VVV;
typedef vector<VVV> VVVV;
typedef vector<VVVV> VVVVV;
typedef vector<VVVV> VVVVVV;
#define MAKEVV(variable, a, ...) VV variable(a, Vec(__VA_ARGS__))
#define MAKEVVc(variable, a, ...) VVc variable(a,Vc(__VA_ARGS__))
#define MAKEVVV(variable, a, b, ...) VVV variable(a, VV(b, Vec(__VA_ARGS__)))
#define MAKEVVVV(variable, a, b, c, ...) VVVV variable(a, VVV(b, (VV(c, Vec(__VA_ARGS__)))))
#define MAKEVVVVV(variable, a, b, c, d, ...) VVVVV variable(a, VVVV(b, (VVV(c, VV(d, Vec(__VA_ARGS__))))))
#define MAKEVVVVVV(variable, a, b, c, d, e, ...) VVVVVV variable(a, VVVVV(b, (VVVV(c, VVV(d, VV(e, Vec(__VA_ARGS__)))))))

#define endl '\n'
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF = 4'000'000'000'000'000'010LL;
const ll MOD=998244353;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define rEach(i, mp) for (auto i = mp.rbegin(); i != mp.rend(); ++i)
#define SUM(a) accumulate(ALL(a),0LL)
#define outminusone(a) cout<< ( a==INF ? -1 : a ) <<endl
#define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end())
#define fi first
#define se second

template<class T, class S>bool chmax(T &a, const S &b) { if (a<b) { a=b; return true; } return false; }
template<class T, class S>bool chmin(T &a, const S &b) { if (b<a) { a=b; return true; } return false; }
template<class T>auto lb(vector<T> &X, T x){return lower_bound(ALL(X),x) - X.begin();}
template<class T>auto ub(vector<T> &X, T x){return upper_bound(ALL(X),x) - X.begin();}
ll popcnt(ll x){return __builtin_popcount(x);}
ll topbit(ll t){return t==0?-1:63-__builtin_clzll(t);}
ll floor(ll y,ll x){assert(x != 0);if(x < 0){y *= -1; x *= -1;}if(y < 0){return (y-x+1)/x;}return y/x;};
ll ceil(ll y, ll x){assert(x != 0);if(x < 0){y *= -1; x *= -1;}if(y < 0){return y/x;}return (y+x-1)/x;};
auto hasbit = [](ll x, ll i )->bool{return (1LL<<i) & x;};//xにi番目のbitが立っているか

template<typename T1, typename T2>
istream &operator>>(istream &i, pair<T1, T2> &p) { return i>>p.first>>p.second; }

template<typename T>
istream &operator>>(istream &i, vector<T> &v) {
    rep(j, v.size())i>>v[j];
    return i;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    bool f = false;
    for(const auto &d: v) {
        if(f) os<<" ";
        f = true;
        os<<d;
    }
    return os;
}

template<class T>
ostream &operator<<(ostream &os, const set<T> &s) {
    os<<"{";
    bool f = false;
    for(auto d: s) {
        if(f) os<<", ";
        f = true;
        os<<d;
    }
    return os<<"}";
}

template<class T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
    os<<"{";
    bool f = false;
    for(auto d: s) {
        if(f) os<<", ";
        f = true;
        os<<d;
    }
    return os<<"}";
}

template<class T, class U>
ostream &operator<<(ostream &os, const map<T, U> &s) {
    bool f = false;
    os<<endl;
    for(auto p: s) {
        if(f) os<<endl;
        f = true;
        os<<p.first<<": "<<p.second;
    }
    return os<<endl;
}

void out() { cout<<endl; }

template<class Head, class... Tail>
void out(const Head &head, const Tail &...tail) {
    cout<<head;
    if(sizeof...(tail)) cout<<' ';
    out(tail...);
}

#ifdef LOCAL
template<typename T>ostream &operator<<(ostream &s, const vector<vector<T>> &vv) {int len=vv.size();for(int i=0; i<len; ++i) {if(i==0)s<<endl;s<<i<<":"<<vv[i];if(i!=len-1)s<<endl;}return s;}
struct PrettyOS {ostream& os;bool first;template <class T> auto operator<<(T&& x) {if (!first) os << ", ";first = false;os << x;return *this;}};
template <class... T> void dbg0(T&&... t) {(PrettyOS{cerr, true} << ... << t);}
#define dbg(...)do {cerr << #__VA_ARGS__ << ":  ";dbg0(__VA_ARGS__);cerr << endl;} while (false);
#else
#define dbg(...)
#endif

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
    int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }
public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
    S all_prod() { return d[1]; }
    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
    void debug(ll n){
        #ifdef LOCAL
        Vec segv;
        rep(i,n){
            segv.pb(prod(i,i+1));
        }
        dbg(segv);
        #endif
    }
private:
    int _n, size, log;
    std::vector<S> d;
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

ll op(ll a, ll b) { return min(a, b); }
ll e() { return INF; }
//segtree<ll,op,e> seg(n)

int solve(){
    ll h,w;
    cin>>h>>w;
    VVc g(h,Vc(w));
    cin>>g;
    VV dp(h,Vec(w,INF));
    segtree<ll,op,e> seg(w);
    segtree<ll,op,e> seg1(w);
    segtree<ll,op,e> seg2(w);
    rep(j,w){
        if(g[h-1][j] == '#')continue;
        dp[h-1][j] = 0;
    }
    per(i,h-2){
        set<ll>st;
        rep(j,w){
            seg.set(j, dp[i+1][j]);
            seg1.set(j,dp[i+1][j] + j);
            seg2.set(j,dp[i+1][j] + w - j);
        }
        seg.debug(w);
        seg1.debug(w);
        seg2.debug(w);
        st.insert(-1);
        st.insert(w);
        rep(j,w){
            if(g[i][j] == '#'){
                st.insert(j);
            }
        }
        rep(j,w){
            if(g[i][j] == '#')continue;
            auto itr = st.lower_bound(j);
            ll R = *itr;
            itr--;
            ll L = *itr + 1;
            dbg(i,j,L,R);
            auto nibutan = [&](ll ok, ll ng, auto f)->ll {
                while (abs(ok-ng) > 1) {
                    ll mid = (ok+ng)/2;
                    tie(ok, ng) = (f(mid) ? mp(mid, ng) : mp(ok, mid));
                }
                return ok;
            };
            auto judge = [&](ll mid)->bool{
                //midが可能か？
                ll r = min(w, j + mid + 1);
                if(r > min(w,R))return false;
                return seg1.prod(r,min(w,R)) <= mid + j;
            };
            auto judge2 = [&](ll mid)->bool{
                //midが可能か？
                ll l = max(0LL,j - mid);
                if(L > l)return false;
                return seg2.prod(L,l) <= mid + w - j;
            };
            auto judge3 = [&](ll mid)->bool{
                //midが可能か？
                ll l = max(0LL,j - mid);
                ll r = min(w, j + mid + 1);
                chmax(l, L);
                chmin(r, R);

                return seg.prod(l,r) <= mid;
            };
            ll ok = nibutan(w+2,-1,judge);
            dbg(ok);
            chmin(ok, nibutan(w+2,-1,judge2));
            dbg(ok)
            chmin(ok, nibutan(w+2,-1,judge3));
            dbg(ok);
            dp[i][j] = ok;
        }
    }
    dbg(dp);
    rep(j,w){
        out(dp[0][j]);
    }
    return  0;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<std::setprecision(20);
//    ll T;
//    cin>>T;
//    while(T--)
    solve();
}
0