結果

問題 No.2657 Falling Block Game
ユーザー GOTKAKO
提出日時 2024-03-01 22:26:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 218 ms / 2,000 ms
コード長 3,082 bytes
コンパイル時間 2,531 ms
コンパイル使用メモリ 217,756 KB
最終ジャッジ日時 2025-02-19 22:46:34
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
int inf = 1e9;
using SS = int;
class DualSegmentTree{
    //作用させるものの交換法則が成り立つ時&&lazy->lazyとlazy->datの作用が同じ時専用.
    //出来ないときは遅延セグ木 出来たとしても改良必須あり.
    public:
    int siz = 1;
    vector<SS> dat;
    void mapping(SS f,SS &x){x = min(f,x);}
    //FF composition(FF f, FF g){mappingと同じ?} チェック.
    SS e(){return inf;}
 
    void make(int N){
        while(siz < N) siz *= 2;
        dat.resize(siz*2,e());
    }
    void make2(int N,vector<SS> &A){
        make(N);
        for(int i=0; i<N; i++) dat.at(i+siz) = A.at(i);
    }
 
    void update(int l,int r,SS x){
        l += siz,r += siz;
        while(l < r){
            if(l&1) mapping(x,dat.at(l)),l++;
            if(r&1) r--,mapping(x,dat.at(r));
            l >>= 1; r >>= 1;
        }
    }
    SS get(int pos){
        pos = pos+siz;
        SS ret = dat.at(pos);
        while(pos != 1){
            pos = pos/2;
            mapping(dat.at(pos),ret);
        }
        return ret;
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int H,W; cin >> H >> W;
    vector<string> S(H);
    for(auto &s : S) cin >> s;
    reverse(S.begin(),S.end());
    vector<vector<int>> toL(H,vector<int>(W)),toR(H,vector<int>(W,W));
    for(int i=0; i<H; i++){
        for(int k=0; k<W; k++){
            if(S.at(i).at(k) == '#') toL.at(i).at(k) = k+1;
            else if(k) toL.at(i).at(k) = toL.at(i).at(k-1);
        }
        for(int k=W-1; k>=0; k--){
            if(S.at(i).at(k) == '#') toR.at(i).at(k) = k;
            else if(k != W-1) toR.at(i).at(k) = toR.at(i).at(k+1);
        }
    }
    vector<DualSegmentTree> dist(H);
    for(auto &d : dist) d.make(W);
    dist.at(0).update(0,W,0);
    for(int i=0; i<H-1; i++){
        for(int k=0; k<W; k++){
            if(S.at(i).at(k) == '#') continue;
            int now = dist.at(i).get(k);
            int l = max(toL.at(i+1).at(k),k-now),r = min(toR.at(i+1).at(k),k+now+1);
            dist.at(i+1).update(l,r,now);
        }
        
        vector<int> next(W);
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> Q;
        for(int k=0; k<W; k++){
            next.at(k) = dist.at(i+1).get(k);
            if(next.at(k) != inf) Q.push({next.at(k),k});
        }
        vector<bool> used(W);
        while(Q.size()){
            auto [nowd,pos] = Q.top(); Q.pop();
            if(used.at(pos)) continue;
            used.at(pos) = true;
            
            if(pos) if(S.at(i+1).at(pos-1) == '.' && next.at(pos-1) > nowd+1){
                next.at(pos-1) = nowd+1; Q.push({nowd+1,pos-1});
            }
            if(pos != W-1) if(S.at(i+1).at(pos+1) == '.' && next.at(pos+1) > nowd+1){
                next.at(pos+1) = nowd+1; Q.push({nowd+1,pos+1});
            }
        }
        DualSegmentTree change; change.make2(W,next);
        dist.at(i+1) = change;
    }
    for(int i=0; i<W; i++) cout << dist.back().get(i) << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0