結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,548 KB
testcase_01 AC 2 ms
6,548 KB
testcase_02 AC 2 ms
6,548 KB
testcase_03 AC 2 ms
6,548 KB
testcase_04 AC 48 ms
23,700 KB
testcase_05 AC 207 ms
16,048 KB
testcase_06 AC 131 ms
14,476 KB
testcase_07 AC 219 ms
16,112 KB
testcase_08 AC 67 ms
13,696 KB
testcase_09 AC 81 ms
28,308 KB
testcase_10 AC 168 ms
14,412 KB
testcase_11 AC 168 ms
14,412 KB
testcase_12 AC 171 ms
14,412 KB
testcase_13 AC 168 ms
14,412 KB
testcase_14 AC 169 ms
14,412 KB
testcase_15 AC 167 ms
14,412 KB
testcase_16 AC 170 ms
14,412 KB
testcase_17 AC 166 ms
14,412 KB
testcase_18 AC 169 ms
14,412 KB
testcase_19 AC 168 ms
14,412 KB
testcase_20 AC 71 ms
13,696 KB
testcase_21 AC 70 ms
13,696 KB
testcase_22 AC 72 ms
13,696 KB
testcase_23 AC 72 ms
13,696 KB
testcase_24 AC 72 ms
13,696 KB
testcase_25 AC 72 ms
13,696 KB
testcase_26 AC 72 ms
13,696 KB
testcase_27 AC 73 ms
13,696 KB
testcase_28 AC 73 ms
13,696 KB
testcase_29 AC 71 ms
13,696 KB
testcase_30 AC 83 ms
28,308 KB
testcase_31 AC 83 ms
28,308 KB
testcase_32 AC 82 ms
28,308 KB
testcase_33 AC 82 ms
28,308 KB
testcase_34 AC 84 ms
28,308 KB
testcase_35 AC 82 ms
28,308 KB
testcase_36 AC 82 ms
28,308 KB
testcase_37 AC 88 ms
28,308 KB
testcase_38 AC 86 ms
28,308 KB
testcase_39 AC 83 ms
28,308 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