結果
問題 | No.2657 Falling Block Game |
ユーザー | ゆにぽけ |
提出日時 | 2024-03-01 23:49:31 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,426 bytes |
コンパイル時間 | 1,644 ms |
コンパイル使用メモリ | 142,364 KB |
実行使用メモリ | 326,400 KB |
最終ジャッジ日時 | 2024-03-01 23:50:16 |
合計ジャッジ時間 | 14,678 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | WA | - |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 2 ms
6,676 KB |
testcase_04 | AC | 8 ms
6,676 KB |
testcase_05 | WA | - |
testcase_06 | AC | 74 ms
9,820 KB |
testcase_07 | AC | 10 ms
6,676 KB |
testcase_08 | AC | 3 ms
6,676 KB |
testcase_09 | AC | 9 ms
6,676 KB |
testcase_10 | AC | 26 ms
9,156 KB |
testcase_11 | AC | 26 ms
9,056 KB |
testcase_12 | AC | 25 ms
8,868 KB |
testcase_13 | AC | 26 ms
9,028 KB |
testcase_14 | AC | 25 ms
8,972 KB |
testcase_15 | AC | 25 ms
8,844 KB |
testcase_16 | AC | 26 ms
8,992 KB |
testcase_17 | AC | 26 ms
8,756 KB |
testcase_18 | AC | 25 ms
8,948 KB |
testcase_19 | AC | 26 ms
8,940 KB |
testcase_20 | AC | 798 ms
316,544 KB |
testcase_21 | AC | 766 ms
311,040 KB |
testcase_22 | AC | 820 ms
325,248 KB |
testcase_23 | AC | 800 ms
326,400 KB |
testcase_24 | AC | 829 ms
325,504 KB |
testcase_25 | AC | 810 ms
325,888 KB |
testcase_26 | AC | 803 ms
326,272 KB |
testcase_27 | AC | 808 ms
319,360 KB |
testcase_28 | AC | 785 ms
320,000 KB |
testcase_29 | AC | 792 ms
321,920 KB |
testcase_30 | AC | 289 ms
112,896 KB |
testcase_31 | AC | 275 ms
109,824 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | AC | 276 ms
109,440 KB |
testcase_38 | WA | - |
testcase_39 | AC | 280 ms
110,848 KB |
ソースコード
#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); } }; 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); const int INF = (int)1e9; for(int i = H - 2;i >= 0;i--) { bool fn = false; for(int j = 0;j < W;j++) { if(S[i][j] == '#') { dp[j] = INF; } if(S[i][j] != '#' && dp[j] == INF) { fn = true; } } if(fn) { vector<int> upd(W); vector<int> n_dp(W,INF); for(int j = 0;j < W;j++) { if(S[i][j] != '#' && dp[j] == INF) { upd[j] = 1; } } for(int j = 0;j < W;) { if(S[i][j] == '#') { j++; } else { int k = j + 1; while(S[i][k] == '.') { k++; } { LiChaoTree<int,0,(int)2e5,(int)1e9> LCT; for(int l = j;l < k;l++) { { if(dp[l] != INF) { LCT.add_segment(0,l + dp[l],0,dp[l]); LCT.add_segment(l + dp[l],(int)2e5,1,-l); } } { n_dp[l] = min(n_dp[l],LCT.query(l)); } } } { LiChaoTree<int,0,(int)2e5,(int)1e9> LCT; for(int l = k - 1;l >= j;l--) { /* if(upd[l]) */ { if(dp[l] != INF) { if(l - dp[l] > 0) { LCT.add_segment(0,l - dp[l],-1,l); } LCT.add_segment(max(0,l - dp[l]),(int)2e5,0,dp[l]); } } { n_dp[l] = min(n_dp[l],LCT.query(l)); } } } j = k; } } 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(); }