結果

問題 No.2657 Falling Block Game
ユーザー GOTKAKOGOTKAKO
提出日時 2024-03-01 22:26:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 213 ms / 2,000 ms
コード長 3,082 bytes
コンパイル時間 2,602 ms
コンパイル使用メモリ 224,344 KB
実行使用メモリ 28,292 KB
最終ジャッジ日時 2024-09-29 14:30:58
合計ジャッジ時間 8,156 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 47 ms
23,540 KB
testcase_05 AC 199 ms
15,948 KB
testcase_06 AC 123 ms
14,352 KB
testcase_07 AC 213 ms
15,920 KB
testcase_08 AC 66 ms
13,568 KB
testcase_09 AC 79 ms
28,148 KB
testcase_10 AC 162 ms
14,416 KB
testcase_11 AC 159 ms
14,416 KB
testcase_12 AC 160 ms
14,308 KB
testcase_13 AC 171 ms
14,288 KB
testcase_14 AC 158 ms
14,284 KB
testcase_15 AC 163 ms
14,284 KB
testcase_16 AC 162 ms
14,284 KB
testcase_17 AC 159 ms
14,284 KB
testcase_18 AC 167 ms
14,288 KB
testcase_19 AC 160 ms
14,416 KB
testcase_20 AC 69 ms
13,568 KB
testcase_21 AC 68 ms
13,440 KB
testcase_22 AC 69 ms
13,568 KB
testcase_23 AC 70 ms
13,568 KB
testcase_24 AC 71 ms
13,568 KB
testcase_25 AC 70 ms
13,568 KB
testcase_26 AC 70 ms
13,440 KB
testcase_27 AC 72 ms
13,568 KB
testcase_28 AC 69 ms
13,440 KB
testcase_29 AC 70 ms
13,440 KB
testcase_30 AC 83 ms
28,212 KB
testcase_31 AC 82 ms
28,232 KB
testcase_32 AC 83 ms
28,152 KB
testcase_33 AC 83 ms
28,292 KB
testcase_34 AC 80 ms
28,244 KB
testcase_35 AC 81 ms
28,248 KB
testcase_36 AC 83 ms
28,084 KB
testcase_37 AC 86 ms
28,216 KB
testcase_38 AC 83 ms
28,236 KB
testcase_39 AC 85 ms
28,248 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0