結果
| 問題 | No.2657 Falling Block Game |
| ユーザー |
 ゆにぽけ
|
| 提出日時 | 2024-03-01 23:20:18 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,503 bytes |
| コンパイル時間 | 1,855 ms |
| コンパイル使用メモリ | 141,416 KB |
| 最終ジャッジ日時 | 2025-02-19 23:13:57 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 WA * 10 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <array>#include <iterator>#include <string>#include <cctype>#include <cstring>#include <cstdlib>#include <cassert>#include <cmath>#include <ctime>#include <iomanip>#include <numeric>#include <stack>#include <queue>#include <map>#include <unordered_map>#include <set>#include <unordered_set>#include <bitset>#include <random>#include <utility>#include <functional>using namespace std;template<class T,T lower_limit,T upper_limit,T id>struct LiChaoTree{private:struct Line{T a,b;Line(T a,T b) : a(a),b(b) {}inline T eval(T x) const{return a * x + b;}};struct Node{Line x;Node *l, *r;Node(const Line &x) : x(x),l(nullptr),r(nullptr) {}};Node *root;Node *add_line(Node *node,Line &x,const T &lower,const T &upper,const T &lower_value,const T &upper_value){if(!node){return new Node(x);}T node_lower_value = node -> x.eval(lower);T node_upper_value = node -> x.eval(upper);if(node_lower_value <= lower_value && node_upper_value <= upper_value){return node;}else if(node_lower_value >= lower_value && node_upper_value >= upper_value){node -> x = x;return node;}else{T mid = (lower + upper) / 2;if(mid == upper){mid--;}T node_mid_value = node -> x.eval(mid),mid_value = x.eval(mid);T nxt_lower_value = lower_value;T nxt_mid_value = mid_value;T nxt_upper_value = upper_value;if(node_mid_value > mid_value){swap(node -> x,x);swap(node_lower_value,nxt_lower_value);swap(node_mid_value,nxt_mid_value);swap(node_upper_value,nxt_upper_value);}if(node_lower_value >= nxt_lower_value){node -> l = add_line(node -> l,x,lower,mid,nxt_lower_value,nxt_mid_value);}else{node -> r = add_line(node -> r,x,mid + 1,upper,nxt_mid_value + x.a,nxt_upper_value);}return node;}}Node *add_segment(Node *node,Line &x,const T &x_l,const T &x_r,const T &lower,const T &upper,const T &lower_value,const T &upper_value){if(upper < x_l || x_r < lower){return node;}if(x_l <= lower && upper <= x_r){Line y = x;return add_line(node,y,lower,upper,lower_value,upper_value);}if(node){T node_lower_value = node -> x.eval(lower);T node_upper_value = node -> x.eval(upper);if(node_lower_value <= lower_value && node_upper_value <= upper_value){return node;}}else{node = new Node(Line(0,id));}T mid = (lower + upper) / 2;if(mid == upper){mid--;}T mid_value = x.eval(mid);node -> l = add_segment(node -> l,x,x_l,x_r,lower,mid,lower_value,mid_value);node -> r = add_segment(node -> r,x,x_l,x_r,mid + 1,upper,mid_value + x.a,upper_value);return node;}T query(const Node *node,const T &x_l,const T &x_r,const T &x) const{if(!node){return id;}T res = node -> x.eval(x);if(x_l == x_r){return res;}T x_m = (x_l + x_r) / 2;if(x_m == x_r){x_m--;}if(x <= x_m){res = min(res,query(node -> l,x_l,x_m,x));}else{res = min(res,query(node -> r,x_m + 1,x_r,x));}return res;}public:LiChaoTree() : root(nullptr) {}void add_line(const T &a,const T &b){Line x(a,b);root = add_line(root,x,lower_limit,upper_limit,x.eval(lower_limit),x.eval(upper_limit));}//[l,r)void add_segment(const T &l,const T &r,const T &a,const T &b){Line x(a,b);root = add_segment(root,x,l,r - 1,lower_limit,upper_limit,x.eval(lower_limit),x.eval(upper_limit));}T query(const T &x) const{assert(lower_limit <= x && x <= upper_limit);return query(root,lower_limit,upper_limit,x);}};#include<algorithm>#include<vector>#include<cassert>using namespace std;struct UnionFind{private:int n;vector<int> par,siz;public:UnionFind(int n) :n(n),par(n,-1),siz(n,1) {}int root(int u){assert(0 <= u && u < n);return (par[u] < 0 ? u:par[u] = root(par[u]));}bool same(int u,int v){assert(0 <= u && u < n && 0 <= v && v < n);return root(u) == root(v);}bool unite(int u,int v){assert(0 <= u && u < n && 0 <= v && v < n);u = root(u),v = root(v);if(u == v) return false;if(siz[u] < siz[v]) swap(u,v);siz[u] += siz[v];par[v] = u;return true;}int size(int u){assert(0 <= u && u < n);return siz[root(u)];}vector<vector<int>> components(){vector<vector<int>> ret(n);for(int u = 0;u < n;u++) ret[root(u)].push_back(u);ret.erase(remove_if(ret.begin(),ret.end(),[](vector<int> v) { return v.empty();}),ret.end());return ret;}};void Main(){int H,W;cin >> H >> W;vector<string> S(H);for(int i = 0;i < H;i++){cin >> S[i];}vector<int> dp(W);for(int i = H - 2;i >= 0;i--){vector<int> n_dp(W,(int)1e9);UnionFind uf(2 * W);for(int j = 0;j < W;j++){if(S[i][j] == '.'){if(j + 1 < W && S[i][j + 1] == '.'){uf.unite(j,j + 1);}if(S[i + 1][j] == '.'){uf.unite(j,j + W);}}if(S[i + 1][j] == '.'){if(j + 1 < W && S[i + 1][j + 1] == '.'){uf.unite(j + W,j + 1 + W);}}}vector<int> L(2 * W,(int)1e9),R(2 * W,-1);for(int j = 0;j < W;j++){int p = uf.root(j);L[p] = min(L[p],j);R[p] = max(R[p],j);}for(int j = 0;j < W;j++){if(S[i][j] == '#'){dp[j] = (int)1e9;}}{LiChaoTree<int,0,(int)2e5,(int)1e9> LCT;for(int j = 0;j < W;j++){if(S[i + 1][j] != '#'){int p = uf.root(j + W);int l = L[p],r = R[p];if(l != (int)1e9){LCT.add_segment(l,min(r + 1,j + dp[j]),0,dp[j]);if(j + dp[j] < r + 1){LCT.add_segment(j + dp[j],r + 1,1,-j);}}}n_dp[j] = min(n_dp[j],LCT.query(j));}}{LiChaoTree<int,0,(int)2e5,(int)1e9> LCT;for(int j = W - 1;j >= 0;j--){if(S[i + 1][j] != '#'){int p = uf.root(j + W);int l = L[p],r = R[p];if(l != (int)1e9){if(j - dp[j] > l){LCT.add_segment(l,min(r + 1,j - dp[j]),-1,j);}LCT.add_segment(max(l,j - dp[j]),r + 1,0,dp[j]);}}n_dp[j] = min(n_dp[j],LCT.query(j));}}swap(dp,n_dp);}for(int i = 0;i < W;i++){cout << dp[i] << "\n";}}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1;/* cin >> tt; */while(tt--) Main();}