Submission #212831

#	Time	Username	Problem	Language	Result	Execution time	Memory
212831		sinatori	Constellation 3 (JOI20_constellation3)	C++14	0 / 100	26 ms	30848 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()

vector<int> G[400010], S[400010];
pair<int, int> P[400010], st[400010];
int W[400010], A[200010], seg[524288], rt[524288], as[1048576], lc[1048576];
vector<pair<int, int>> H;
vector<int> T[400010];
tuple<int, int, int> R[400010];
int par[400010];
set<int> soko;
ll arr[400010];
queue<int> Q;

int hlnum[400010], hlseg[400010], hltop[400010], hlpar[400010];
//hlnumはhl分解後の「セグ木上での番号」、hlsegはhl分解後のセグ木のx番目の「頂点番号」、hltopはその頂点が属する鎖の一番根に近いやつの「頂点番号」、hlparは鎖の繋がっている親ノードの「頂点番号」

int wgh(int x) {
	if (T[x].size() == 0) {
		W[x] = 1;
		return 1;
	}
	int a = 1;
	for (int j : T[x])a += wgh(j);
	W[x] = a;
	return a;
}

void hld(int x, int me, int& num) {
	int mw = 0, ms = 0;
	hlnum[x] = num;
	hlseg[num] = x;
	hltop[x] = me;
	if (T[x].size() == 0)return;
	for (int i : T[x]) {
		if (W[i] > mw)ms = i, mw = W[i];
	}
	num++;
	hld(ms, me, num);
	for (int i : T[x]) {
		if (i != ms) {
			hlpar[i] = x;
			num++;
			hld(i, i, num);
		}
	}
}

void raq_as(int s, int t, ll v, int k = 1, int l = 0, int r = 524287) {
	if (t < l || r < s)return;
	if (s <= l && r <= t) {
		as[k] += v;
		return;
	}
	raq_as(s, t, v, k * 2, l, (l + r) / 2);
	raq_as(s, t, v, k * 2 + 1, (l + r) / 2 + 1, r);
}

ll rsq_lc(int s, int t, int k = 1, int l = 0, int r = 524287) {
	if (t < l || r < s)return 0;
	if (s <= l && r <= t) {
		return lc[k];
	}
	ll lv = rsq_lc(s, t, k * 2, l, (l + r) / 2);
	ll rv = rsq_lc(s, t, k * 2 + 1, (l + r) / 2 + 1, r);
	return lv + rv;
}

void add_lc(int x, ll v) {
	x += 524288;
	while (x) {
		lc[x] += v;
		x /= 2;
	}
	return;
}

ll get_as(int x) {
	x += 524288;
	ll ans = 0;
	while (x) {
		ans += as[x];
		x /= 2;
	}
	return ans;
}

void solve2(int x, ll dif) {
	int tp = hlnum[x];
	int tpp = hlnum[hltop[x]];
	add_lc(tp, dif);//lcへの加算
	raq_as(tpp, tp, dif);//asの加算
	if (hlpar[hltop[x]] == 0)return;
	solve2(hlpar[hltop[x]], dif);
}

void solve(int x, int y, ll val, bool fir = 0) {
	int tp = hlnum[x];//セグ木上での番号
	int tpp = hlnum[hltop[x]];//鎖のtopのセグ木上での番号

	if (fir) {
		val += rsq_lc(tp, tp);
	}
	if (get<2>(R[hltop[x]]) < y) {
		val += rsq_lc(tpp, tp - 1);//lcの和
		if (T[x].size()) {
			val += get_as(tp + 1);//asの点取得
		}
		solve(hlpar[hltop[x]], y, val);
	}
	else {
		int ok = tpp, ng = tp + 1, mid;
		while (ok + 1 != ng) {
			mid = (ok + ng) / 2;
			if (get<2>(R[hlseg[mid]]) < y) {
				ng = mid;
			}
			else {
				ok = mid;
			}
		}

		val += rsq_lc(ok, tp - 1);//lcの和
		if (T[x].size())
			val += get_as(tp + 1);
		ll alr = get_as(ok);
		if (alr < val) {
			raq_as(tpp, ok, val - alr);//asの加算
			solve2(hlpar[hltop[x]], val - alr);
		}
	}
}

int rmq(int s, int t, int k = 1, int l = 0, int r = 262143) {
	if (t < l || r < s)return INT32_MIN;
	if (s <= l && r <= t) {
		return seg[k];
	}
	int lv = rmq(s, t, k * 2, l, (l + r) / 2);
	int rv = rmq(s, t, k * 2 + 1, (l + r) / 2 + 1, r);
	return max(lv, rv);
}

void ruq(int s, int t, int v, int k = 1, int l = 0, int r = 262143) {
	if (t < l || r < s)return;
	if (s <= l && r <= t) {
		rt[k] = v;
		return;
	}
	if (rt[k]) {
		rt[k * 2] = rt[k];
		rt[k * 2 + 1] = rt[k];
		rt[k] = 0;
	}
	ruq(s, t, v, k * 2, l, (l + r) / 2);
	ruq(s, t, v, k * 2 + 1, (l + r) / 2 + 1, r);
}

int gets(int x) {
	x += 262144;
	int ans = 0;
	while (x) {
		if (rt[x])ans = rt[x];
		x /= 2;
	}
	return ans;
}

void say(tuple<int, int, int>X) {
	int a, b, c;
	tie(a, b, c) = X;
	cout << a << " " << b << " " << c << endl;
}

void make_skytree(int l, int r, int& num) {
	int m = rmq(l, r), me = num;
	pair<int, int> ser = { m,l };
	auto it = lower_bound(all(H), ser);
	ser = { m,r + 1 };
	auto it2 = lower_bound(all(H), ser);

	int li = l, t;

	for (auto i = it;;i++) {
		if (i == it2)
			t = r;
		else {
			t = (*i).second - 1;
			ruq(t + 1, t + 1, me);
		}
		if (li <= t) {
			num++;
			ruq(li, t, num);
			T[me].push_back(num);
			R[num] = make_tuple(li, t, m);
			par[num] = me;
			make_skytree(li, t, num);
		}
		li = t + 2;

		if (i == it2)break;
	}

	if (T[me].size() == 0) {
		Q.push(me);
	}
}

int main() {
	for (int i = 0;i < 524288;i++)seg[i] = 0;
	int N, M;
	cin >> N;
	R[1] = make_tuple(1, N, N + 3);
	for (int i = 0;i < N;i++) {
		cin >> A[i];
		seg[i + 262145] = A[i];
		H.push_back({ A[i],i + 1 });
	}
	sort(all(H));

	for (int i = 262143;i >= 0;i--) {
		seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
	}
	par[1] = 0;
	int a = 1;
	make_skytree(1, N, a);

	wgh(1);
	st[1] = { 1,0 };
	P[1] = { 0,0 };
	a = 1;
	hld(1, 1, a);

	cin >> M;
	ll X, Y, C, xi, alc = 0;
	vector<tuple<ll, ll, ll>> V(M);
	for (int i = 0;i < M;i++) {
		cin >> X >> Y >> C;
		xi = gets(X);
		alc += C;
		V[i] = make_tuple(Y, xi, C);
	}

	sort(all(V));

	int bef = 0;
	ll ans;
	for (int i = 0;i < M;i++) {
		tie(Y, xi, C) = V[i];

		solve(xi, Y, C, 1);
	}

	cout << alc - get_as(1) << endl;
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:248:6: warning: unused variable 'bef' [-Wunused-variable]
  int bef = 0;
      ^~~
constellation3.cpp:249:5: warning: unused variable 'ans' [-Wunused-variable]
  ll ans;
     ^~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 65