Submission #444937

#	Time	Username	Problem	Language	Result	Execution time	Memory
444937		flappybird	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	1102 ms	132112 KiB

constellation3

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAX 301010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
struct Star {
	ll x, y, c, ban;
	Star() :x(0), y(0), c(0), ban(0) {}
	Star(ll x, ll y, ll c) :x(x), y(y), c(c), ban(0) {}
};
struct segtree {
	vector<ll> l, r, tree;
	ll s;
	ll type;
	void init(ll x = 1) {
		if (x >= s) {
			l[x] = r[x] = x - s + 1;
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
		if (type == 1) tree[x] = tree[x * 2] + tree[x * 2 + 1];
		else tree[x] = max(tree[x * 2], tree[x * 2 + 1]);		
	}
	void update(ll x, ll a) {
		x += s - 1;
		tree[x] = a;
		x /= 2;
		while (x) {
			if (type == 1) tree[x] = tree[x * 2] + tree[x * 2 + 1];
			else tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
			x /= 2;
		}
	}
	ll query(ll low, ll high, ll loc = 1) {
		if (l[loc] == low && r[loc] == high) return tree[loc];
		if (high <= r[loc * 2]) return query(low, high, loc * 2);
		if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
		if (type == 1) return query(low, r[loc * 2], loc * 2) + query(l[loc * 2 + 1], high, loc * 2 + 1);
		else return max(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
	}
	segtree(ll N) {
		type = 1;
		s = 1LL << (ll)ceil(log2(N));
		tree.resize(2 * s + 1);
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
	}
	segtree() {

	}
};
ll A[MAX];
ll lc[MAX], rc[MAX];
ll sp[MAX][MAXS];
ll bottom[MAX], revb[MAX];
ll sz[MAX];
ll sum[MAX];
ll ans[MAX];
ll depth[MAX];
Star star[MAX];
vector<ll> cart[MAX];
vector<vector<ll>> chain;
pll cnum[MAX];
vector<segtree> chainseg;
ll S, N, M;
ll cnt;
segtree aseg;
ll make_tree(ll l, ll r, ll num, ll p, ll d) {
	sz[num] = r - l + 1;
	ll res = aseg.query(l, r);
	ll mid = res % 1000000;
	bottom[mid] = num;
	depth[num] = d;
	revb[num] = mid;
	sp[num][0] = p;
	for (ll i = 1; i < MAXS; i++) sp[num][i] = sp[sp[num][i - 1]][i - 1];
	if (l <= mid - 1) lc[num] = make_tree(l, mid - 1, ++S, num, d + 1);
	else lc[num] = 0;
	if (mid + 1 <= r) rc[num] = make_tree(mid + 1, r, ++S, num, d + 1);
	else rc[num] = 0;
	return num;
}
void assign_star() {
	ll i, j;
	for (i = 1; i <= M; i++) {
		ll v = bottom[star[i].x];
		star[i].ban = v;
		for (j = MAXS - 1; j >= 0; j--) {
			if (A[revb[sp[v][j]]] < star[i].y) v = sp[v][j];
		}
		cart[v].push_back(i);
	}
}
void make_chain(ll x, ll p = 0) {
	chain[cnt].push_back(x);
	cnum[x] = { cnt, chain[cnt].size() - 1 };
	ll a, b;
	a = lc[x], b = rc[x];
	if (sz[lc[x]] < sz[rc[x]]) swap(a, b);
	if (a) make_chain(a, x);
	if (b) {
		cnt++;
		chain.push_back(vector<ll>());
		make_chain(b, x);
	}
}
void make_seg() {
	for (ll i = 0; i < chain.size(); i++) chainseg.push_back(segtree(chain[i].size()));
	for (ll i = 0; i < chain.size(); i++) chainseg[i].init();
}
ll lca(ll u, ll v) {
	if (!(u * v)) return -1;
	if (u == v) return u;
	ll i;
	if (depth[u] != depth[v]) {
		if (depth[u] > depth[v]) swap(u, v);
		for (i = MAXS - 1; i >= 0; i--) if (depth[sp[v][i]] >= depth[u]) v = sp[v][i];
	}
	if (u == v) return u;
	for (i = MAXS - 1; i >= 0; i--) if (sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i];
	return sp[u][0];
}
void update(ll x, ll a) {
	if (!x) return;
	chainseg[cnum[x].first].update(cnum[x].second + 1, a);
}
ll f(ll x) {
	ll s;
	if (lc[sp[x][0]] == x) s = rc[sp[x][0]];
	else s = lc[sp[x][0]];
	return s;
}
ll query(ll u, ll v) {
	ll ret = 0;
	ll l = lca(u, v);
	while (cnum[u].first != cnum[l].first) ret += chainseg[cnum[u].first].query(1, cnum[u].second + 1), u = sp[chain[cnum[u].first][0]][0];
	while (cnum[v].first != cnum[l].first) ret += chainseg[cnum[v].first].query(1, cnum[v].second + 1), v = sp[chain[cnum[v].first][0]][0];
	ret += chainseg[cnum[l].first].query(cnum[l].second + 1, cnum[u].second + 1);
	ret += chainseg[cnum[l].first].query(cnum[l].second + 1, cnum[v].second + 1);
	ret -= chainseg[cnum[l].first].query(cnum[l].second + 1, cnum[l].second + 1);
	return ret;
}
void calc(ll x = 1, ll p = 0) {
	if (!x) return;
	calc(lc[x]);
	calc(rc[x]);
	sum[x] = ans[lc[x]] + ans[rc[x]];
	ans[x] = sum[x];
	for (auto asdf : cart[x]) {
		Star st = star[asdf];
		ll b = st.ban;
		if (b == x) ans[x] = max(sum[x] + st.c, ans[x]);
		else {
			ll s;
			if (lca(b, lc[x]) == lc[x]) s = lc[x];
			else s = rc[x];
			ans[x] = max(sum[b] + query(b, s) + st.c, ans[x]);
		}
	}
	if (x != 1) update(f(x), ans[x]);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N;
	A[0] = INF;
	ll i;
	aseg = segtree(N);
	aseg.type = 0;
	for (i = 1; i <= N; i++) cin >> A[i], aseg.tree[i + aseg.s - 1] = 1000000 * A[i] + i;
	aseg.init();
	cin >> M;
	ll asdfsdf = 0;
	for (i = 1; i <= M; i++) cin >> star[i].x >> star[i].y >> star[i].c, asdfsdf += star[i].c;
	S = 1;
	make_tree(1, N, 1, 0, 1);
	assign_star();
	chain.push_back(vector<ll>());
	make_chain(1);
	make_seg();
	calc();
	cout << asdfsdf - ans[1] << ln;
}

Compilation message (stderr)

constellation3.cpp: In function 'void make_seg()':
constellation3.cpp:119:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for (ll i = 0; i < chain.size(); i++) chainseg.push_back(segtree(chain[i].size()));
      |                 ~~^~~~~~~~~~~~~~
constellation3.cpp:120:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for (ll i = 0; i < chain.size(); i++) chainseg[i].init();
      |                 ~~^~~~~~~~~~~~~~
constellation3.cpp: In function 'll lca(ll, ll)':
constellation3.cpp:123:10: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
  123 |  if (!(u * v)) return -1;
      |       ~~~^~~~

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