結果

問題 No.2657 Falling Block Game
ユーザー GOTKAKOGOTKAKO
提出日時 2024-03-01 22:22:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,963 bytes
コンパイル時間 2,527 ms
コンパイル使用メモリ 223,644 KB
実行使用メモリ 28,304 KB
最終ジャッジ日時 2024-09-29 14:24:01
合計ジャッジ時間 8,109 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 1 ms
6,824 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 44 ms
23,420 KB
testcase_05 AC 206 ms
15,924 KB
testcase_06 AC 128 ms
14,352 KB
testcase_07 AC 215 ms
15,992 KB
testcase_08 AC 66 ms
13,568 KB
testcase_09 AC 78 ms
28,268 KB
testcase_10 AC 159 ms
14,412 KB
testcase_11 AC 161 ms
14,284 KB
testcase_12 AC 161 ms
14,416 KB
testcase_13 AC 166 ms
14,412 KB
testcase_14 AC 167 ms
14,288 KB
testcase_15 AC 163 ms
14,416 KB
testcase_16 AC 164 ms
14,412 KB
testcase_17 AC 167 ms
14,412 KB
testcase_18 AC 170 ms
14,420 KB
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 AC 75 ms
28,200 KB
testcase_31 AC 76 ms
28,108 KB
testcase_32 AC 74 ms
28,204 KB
testcase_33 AC 75 ms
28,152 KB
testcase_34 AC 76 ms
28,220 KB
testcase_35 AC 77 ms
28,180 KB
testcase_36 AC 78 ms
28,304 KB
testcase_37 AC 79 ms
28,260 KB
testcase_38 AC 77 ms
28,300 KB
testcase_39 AC 77 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});
        }
        while(Q.size()){
            auto [nowd,pos] = Q.top(); Q.pop();
            if(pos) if(S.at(i+1).at(pos-1) == '.' && next.at(pos-1) == inf){
                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) == inf){
                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