#956991 (C++17) No.2657 Falling Block Game

提出ソース

結果

問題	No.2657 Falling Block Game
ユーザー	ゆにぽけ
提出日時	2024-03-01 23:17:31
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,422 bytes
コンパイル時間	1,575 ms
コンパイル使用メモリ	146,552 KB
実行使用メモリ	306,304 KB
最終ジャッジ日時	2024-09-29 15:08:56
合計ジャッジ時間	19,311 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	291 ms 171,904 KB
testcase_05	AC	288 ms 21,720 KB
testcase_06	AC	120 ms 6,820 KB
testcase_07	AC	720 ms 57,648 KB
testcase_08	AC	831 ms 66,688 KB
testcase_09	AC	1,000 ms 306,304 KB
testcase_10	AC	70 ms 12,216 KB
testcase_11	AC	69 ms 12,152 KB
testcase_12	AC	67 ms 12,184 KB
testcase_13	AC	70 ms 12,204 KB
testcase_14	AC	70 ms 12,200 KB
testcase_15	AC	71 ms 12,088 KB
testcase_16	AC	69 ms 12,116 KB
testcase_17	AC	64 ms 12,012 KB
testcase_18	AC	67 ms 12,148 KB
testcase_19	AC	69 ms 12,192 KB
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	896 ms 302,620 KB
testcase_31	AC	901 ms 302,224 KB
testcase_32	AC	900 ms 302,848 KB
testcase_33	AC	905 ms 302,848 KB
testcase_34	AC	928 ms 302,848 KB
testcase_35	AC	911 ms 302,848 KB
testcase_36	AC	901 ms 302,836 KB
testcase_37	AC	884 ms 300,596 KB
testcase_38	AC	904 ms 302,756 KB
testcase_39	AC	848 ms 295,296 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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];
					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(j - dp[j] > l)
					{
						LCT.add_segment(l,min(r + 1,j - dp[j]),-1,j);
					}
					LCT.add_segment(max(l,j - dp[j]),(int)2e5,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();
}

yukicoder

結果

テストケース

ソースコード