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

提出ソース

結果

問題	No.2861 Slime Party
ユーザー	square1001
提出日時	2024-07-25 20:40:20
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,822 ms / 4,000 ms
コード長	5,174 bytes
コンパイル時間	1,606 ms
コンパイル使用メモリ	99,464 KB
実行使用メモリ	43,676 KB
最終ジャッジ日時	2024-08-25 17:32:29
合計ジャッジ時間	63,854 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	331 ms 43,612 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	5 ms 6,944 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	5 ms 6,944 KB
testcase_14	AC	5 ms 6,940 KB
testcase_15	AC	5 ms 6,940 KB
testcase_16	AC	3 ms 6,944 KB
testcase_17	AC	4 ms 6,944 KB
testcase_18	AC	4 ms 6,944 KB
testcase_19	AC	3 ms 6,940 KB
testcase_20	AC	3 ms 6,940 KB
testcase_21	AC	1,122 ms 33,636 KB
testcase_22	AC	1,032 ms 33,640 KB
testcase_23	AC	1,053 ms 33,588 KB
testcase_24	AC	1,026 ms 33,656 KB
testcase_25	AC	1,183 ms 33,496 KB
testcase_26	AC	868 ms 33,564 KB
testcase_27	AC	885 ms 33,576 KB
testcase_28	AC	867 ms 33,472 KB
testcase_29	AC	873 ms 33,404 KB
testcase_30	AC	908 ms 33,576 KB
testcase_31	AC	1,227 ms 33,572 KB
testcase_32	AC	1,207 ms 33,412 KB
testcase_33	AC	1,230 ms 33,580 KB
testcase_34	AC	1,248 ms 33,428 KB
testcase_35	AC	1,215 ms 33,496 KB
testcase_36	AC	1,288 ms 33,428 KB
testcase_37	AC	1,269 ms 33,588 KB
testcase_38	AC	1,300 ms 33,596 KB
testcase_39	AC	1,246 ms 33,408 KB
testcase_40	AC	1,290 ms 33,428 KB
testcase_41	AC	1,130 ms 33,564 KB
testcase_42	AC	1,144 ms 33,500 KB
testcase_43	AC	1,131 ms 33,612 KB
testcase_44	AC	1,201 ms 33,404 KB
testcase_45	AC	1,108 ms 33,576 KB
testcase_46	AC	1,288 ms 33,404 KB
testcase_47	AC	1,303 ms 33,604 KB
testcase_48	AC	1,245 ms 33,568 KB
testcase_49	AC	1,302 ms 33,600 KB
testcase_50	AC	1,294 ms 33,464 KB
testcase_51	AC	424 ms 43,660 KB
testcase_52	AC	421 ms 43,676 KB
testcase_53	AC	431 ms 43,620 KB
testcase_54	AC	424 ms 43,648 KB
testcase_55	AC	427 ms 43,476 KB
testcase_56	AC	441 ms 43,676 KB
testcase_57	AC	454 ms 43,572 KB
testcase_58	AC	442 ms 43,576 KB
testcase_59	AC	451 ms 43,596 KB
testcase_60	AC	453 ms 43,656 KB
testcase_61	AC	436 ms 43,568 KB
testcase_62	AC	461 ms 43,628 KB
testcase_63	AC	434 ms 43,544 KB
testcase_64	AC	413 ms 43,588 KB
testcase_65	AC	1,252 ms 43,508 KB
testcase_66	AC	1,822 ms 43,580 KB
testcase_67	AC	325 ms 43,660 KB
testcase_68	AC	1,146 ms 43,504 KB
testcase_69	AC	541 ms 43,504 KB
testcase_70	AC	649 ms 43,584 KB
testcase_71	AC	463 ms 43,640 KB
testcase_72	AC	1,210 ms 43,480 KB
testcase_73	AC	1,098 ms 43,580 KB
testcase_74	AC	1,144 ms 43,536 KB
testcase_75	AC	389 ms 43,476 KB

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

ソースコード

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;
public:
	heavy_light(const vector<int>& par_) : n(par_.size()), par(par_), seg(n) {
		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) {
		seg.range_add(id[v], id[v] + 1, x);
	}
	void add_path(int v, long long x) {
		while (v != -1) {
			seg.range_add(id[head[v]], id[v] + 1, x);
			v = par[head[v]];
		}
	}
	long long get_vertex(int 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 (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

結果

テストケース

ソースコード