#997383 (C++17) No.2861 Slime Party

提出ソース

結果

問題	No.2861 Slime Party
ユーザー	square1001
提出日時	2024-07-25 20:39:36
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	5,439 bytes
コンパイル時間	1,464 ms
コンパイル使用メモリ	94,336 KB
実行使用メモリ	52,072 KB
最終ジャッジ日時	2024-07-25 20:39:58
合計ジャッジ時間	20,599 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	3 ms 5,376 KB
testcase_14	AC	3 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	3 ms 5,376 KB
testcase_17	AC	3 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	3 ms 5,376 KB
testcase_20	AC	188 ms 35,088 KB
testcase_21	AC	190 ms 35,072 KB
testcase_22	AC	187 ms 35,024 KB
testcase_23	AC	178 ms 35,160 KB
testcase_24	AC	187 ms 35,072 KB
testcase_25	AC	175 ms 35,164 KB
testcase_26	AC	176 ms 35,072 KB
testcase_27	AC	171 ms 35,000 KB
testcase_28	AC	173 ms 35,160 KB
testcase_29	AC	173 ms 35,196 KB
testcase_30	AC	189 ms 34,996 KB
testcase_31	AC	193 ms 35,072 KB
testcase_32	AC	189 ms 35,188 KB
testcase_33	AC	199 ms 35,132 KB
testcase_34	AC	193 ms 35,096 KB
testcase_35	AC	185 ms 35,124 KB
testcase_36	AC	185 ms 35,164 KB
testcase_37	AC	185 ms 35,072 KB
testcase_38	AC	200 ms 35,108 KB
testcase_39	AC	191 ms 35,200 KB
testcase_40	AC	194 ms 35,080 KB
testcase_41	AC	191 ms 35,184 KB
testcase_42	AC	190 ms 35,000 KB
testcase_43	AC	197 ms 35,024 KB
testcase_44	AC	197 ms 35,104 KB
testcase_45	AC	180 ms 35,064 KB
testcase_46	AC	190 ms 35,200 KB
testcase_47	AC	189 ms 35,072 KB
testcase_48	AC	188 ms 35,072 KB
testcase_49	AC	195 ms 35,124 KB
testcase_50	TLE	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-
testcase_57	--	-
testcase_58	--	-
testcase_59	--	-
testcase_60	--	-
testcase_61	--	-
testcase_62	--	-
testcase_63	--	-
testcase_64	--	-
testcase_65	--	-
testcase_66	--	-
testcase_67	--	-
testcase_68	--	-
testcase_69	--	-
testcase_70	--	-
testcase_71	--	-
testcase_72	--	-
testcase_73	--	-
testcase_74	--	-

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

ソースコード

raw source code

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const long long INF = 3LL << 59;

class query {
public:
	int t, a; long long b;
	query() : t(-1), a(-1), b(-1) {}
};

class node {
public:
	int p, l, r;
	node() : p(-1), l(-1), r(-1) {}
};

class binary_tree {
public:
	int root;
	vector<node> v;
	binary_tree(int n) : root(-1), v(vector<node>(n)) {}
};

binary_tree cartesian_tree(int N, const vector<long long>& A) {
	binary_tree T(N);
	vector<int> st;
	int pos = 0;
	for (int i = 0; i < N; i++) {
		int u = -1;
		while (!st.empty() && A[st.back()] < A[i]) {
			u = st.back();
			st.pop_back();
		}
		if (u != -1) {
			T.v[i].l = u;
			T.v[u].p = i;
		}
		if (!st.empty()) {
			T.v[i].p = st.back();
			T.v[st.back()].r = i;
		}
		st.push_back(i);
	}
	T.root = st[0];
	return T;
}

class segment_tree {
	// range add / range max
private:
	int size;
	vector<long long> v;
	vector<long long> lazy;
	void push(int k) {
		v[k] += lazy[k];
		if (k < size) {
			lazy[k * 2 + 0] += lazy[k];
			lazy[k * 2 + 1] += lazy[k];
		}
		lazy[k] = 0;
	}
public:
	segment_tree(int n) : size(1 << (n >= 2 ? 32 - __builtin_clz(n - 1) : 0)), v(size * 2), lazy(size * 2) {}
	void range_add(int l, int r, long long x) {
		auto recur = [&](auto& self, int k, int s, int t) -> void {
			if (l <= s && t <= r) {
				lazy[k] += x;
				push(k);
				return;
			}
			push(k);
			if (r <= s || t <= l) {
				return;
			}
			self(self, k * 2 + 0, s, (s + t) / 2);
			self(self, k * 2 + 1, (s + t) / 2, t);
			v[k] = max(v[k * 2 + 0], v[k * 2 + 1]);
		};
		recur(recur, 1, 0, size);
	}
	long long range_max(int l, int r) {
		auto recur = [&](auto& self, int k, int s, int t) -> long long {
			push(k);
			if (l <= s && t <= r) {
				return v[k];
			}
			if (r <= s || t <= l) {
				return -INF;
			}
			long long zl = self(self, k * 2 + 0, s, (s + t) / 2);
			long long zr = self(self, k * 2 + 1, (s + t) / 2, t);
			v[k] = max(v[k * 2 + 0], v[k * 2 + 1]);
			return max(zl, zr);
		};
		return recur(recur, 1, 0, size);
	}
};

class heavy_light {
private:
	int n;
	vector<int> par;
	vector<int> id;
	vector<int> id_vertex;
	vector<int> head;
	segment_tree seg;
	vector<long long> base;
public:
	heavy_light(const vector<int>& par_) : n(par_.size()), par(par_), seg(n) {
		base = vector<long long>(n, 0);
		vector<vector<int> > g(n);
		int root = -1;
		for (int i = 0; i < n; i++) {
			if (par[i] != -1) {
				g[par[i]].push_back(i);
			} else {
				root = i;
			}
		}
		vector<int> subsize(n, 1);
		auto build_order = [&](auto& self, int v) -> void {
			for (int &i : g[v]) {
				self(self, i);
				subsize[v] += subsize[i];
				if (subsize[i] > subsize[g[v][0]]) {
					swap(g[v][0], i);
				}
			}
		};
		build_order(build_order, root);
		int cur = 0;
		id.resize(n);
		id_vertex.resize(n);
		head.resize(n);
		auto build_tree = [&](auto& self, int v) -> void {
			id[v] = cur;
			id_vertex[cur] = v;
			cur++;
			for (int i : g[v]) {
				head[i] = (i == g[v][0] ? head[v] : i);
				self(self, i);
			}
		};
		head[root] = root;
		build_tree(build_tree, root);
	}
	void add_vertex(int v, long long x) {
		base[v] += x;
		// seg.range_add(id[v], id[v] + 1, x);
	}
	void add_path(int v, long long x) {
		while (v != -1) {
			base[v] += x;
			v = par[v];
		}
		/*
		while (v != -1) {
			seg.range_add(id[head[v]], id[v] + 1, x);
			v = par[head[v]];
		}
		*/
	}
	long long get_vertex(int v) {
		return base[v];
		// return seg.range_max(id[v], id[v] + 1);
	}
	int query(int v, long long x) {
		// first unreachable ancestor from v by only passing vertex with < x
		while (v != -1) {
			if (base[v] >= x) {
				break;
			}
			v = par[v];
		}
		return v;
		/*
		while (v != -1) {
			if (seg.range_max(id[head[v]], id[v] + 1) >= x) {
				break;	
			}
			v = par[head[v]];
		}
		if (v == -1) {
			return -1;
		}
		int l = id[head[v]], r = id[v] + 1;
		while (r - l > 1) {
			int m = (l + r) / 2;
			if (seg.range_max(m, id[v] + 1) >= x) {
				l = m;
			} else {
				r = m;
			}
		}
		return id_vertex[l];
		*/
	}
};

vector<long long> solve(int N, int Q, long long L, const vector<long long>& A, const vector<long long>& X, const vector<query>& qs) {
	binary_tree T = cartesian_tree(N, A);
	vector<int> par(N);
	for (int i = 0; i < N; i++) {
		par[i] = T.v[i].p;
	}
	heavy_light hld(par);
	for (int i = 0; i < N; i++) {
		hld.add_path(i, -X[i]);
		if (i != T.root) {
			hld.add_vertex(i, A[par[i]]);
		}
	}
	vector<long long> CX = X;
	vector<long long> ans;
	for (query q : qs) {
		if (q.t == 1) {
			long long d = q.b - CX[q.a];
			CX[q.a] = q.b;
			hld.add_path(q.a, -d);
		}
		if (q.t == 2) {
			int base = (A[q.a] < A[q.a + 1] ? q.a : q.a + 1);
			if (A[base] < L) {
				int pos = hld.query(base, L);
				if (pos == -1) {
					pos = T.root;
				}
				long long subans = hld.get_vertex(pos);
				ans.push_back(-(subans - (pos != T.root ? A[T.v[pos].p] : 0)) + L);
			} else {
				ans.push_back(L);
			}
		}
	}
	return ans;
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int N, Q; long long L;
	cin >> N >> Q >> L;
	vector<long long> A(N), X(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> X[i];
	}
	vector<query> qs(Q);
	for (int i = 0; i < Q; i++) {
		cin >> qs[i].t >> qs[i].a;
		if (qs[i].t == 1) {
			cin >> qs[i].b;
		}
		qs[i].a--;
	}
	vector<long long> ans = solve(N, Q, L, A, X, qs);
	for (int i = 0; i < int(ans.size()); i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード