結果

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

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/segtree>
using namespace std;
int op(int a, int b){return a<b?a:b;}
int e(){return 1<<30;}
int H,W,L[1<<17],R[1<<17];
string S[1<<17];
int dp[1<<17],ep[1<<17];
void initLR(int i)
{
    L[0]=0;
    for(int j=1;j<W;j++)L[j]=(S[i][j]=='#'?j+1:L[j-1]);
    R[W]=W;
    for(int j=W-1;j>=0;j--)R[j]=(S[i][j]=='#'?j:R[j+1]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>H>>W;
    for(int i=0;i<H;i++)cin>>S[i];
    for(int i=H-2;i>=0;i--)
    {
        initLR(i);
        for(int j=0;j<W;j++)ep[j]=1<<30;
        atcoder::segtree<int,op,e>seg(W);
        for(int j=0;j<W;j++)seg.set(j,dp[j]);
        for(int j=0;j<W;j++)if(S[i][j]!='#')
        {
            int l=-1,r=W;
            while(r-l>1)
            {
                int m=(l+r)/2;
                int f=seg.prod(max(L[j],j-m),min(R[j],j+m+1));
                if(f<=m)r=m;
                else l=m;
            }
            ep[j]=r;
        }
        // for(int j=0;j<W;j++)cout<<(ep[j]==1<<30?-1:ep[j])<<' ';cout<<endl;
        swap(dp,ep);
    }
    for(int i=0;i<W;i++)cout<<dp[i]<<endl;
}
0