oj.uz

Submission #212876

# Submission time Handle Problem Language Result Execution time Memory
212876 2020-03-24T12:26:49 Z sinatori Constellation 3 (JOI20_constellation3) C++14
0 / 100
 37 ms 50128 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()

ll 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];

ll 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;
	hlpar[x] = hlpar[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 < s)return;
	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 < s)return 0;
	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[x] == 0)return;
	solve2(hlpar[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;
	}
}

int main() {
	for (int i = 0;i < 524288;i++)seg[i] = 0, rt[i] = 0;
	for (int i = 0;i < 1048576;i++)as[i] = 0, lc[i] = 0;
	for (int i = 0;i < 400010;i++)W[i] = hlnum[i] = hlseg[i] = hltop[i] = hlpar[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);
	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;
	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

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 50040 KB Output is correct
2 Correct 37 ms 49988 KB Output is correct
3 Correct 33 ms 50040 KB Output is correct
4 Correct 32 ms 50048 KB Output is correct
5 Correct 31 ms 50040 KB Output is correct
6 Correct 35 ms 50128 KB Output is correct
7 Correct 33 ms 50048 KB Output is correct
8 Correct 32 ms 50048 KB Output is correct
9 Correct 33 ms 50040 KB Output is correct
10 Correct 31 ms 50040 KB Output is correct
11 Correct 32 ms 50048 KB Output is correct
12 Correct 32 ms 50048 KB Output is correct
13 Correct 32 ms 50048 KB Output is correct
14 Incorrect 32 ms 50048 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 50040 KB Output is correct
2 Correct 37 ms 49988 KB Output is correct
3 Correct 33 ms 50040 KB Output is correct
4 Correct 32 ms 50048 KB Output is correct
5 Correct 31 ms 50040 KB Output is correct
6 Correct 35 ms 50128 KB Output is correct
7 Correct 33 ms 50048 KB Output is correct
8 Correct 32 ms 50048 KB Output is correct
9 Correct 33 ms 50040 KB Output is correct
10 Correct 31 ms 50040 KB Output is correct
11 Correct 32 ms 50048 KB Output is correct
12 Correct 32 ms 50048 KB Output is correct
13 Correct 32 ms 50048 KB Output is correct
14 Incorrect 32 ms 50048 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 50040 KB Output is correct
2 Correct 37 ms 49988 KB Output is correct
3 Correct 33 ms 50040 KB Output is correct
4 Correct 32 ms 50048 KB Output is correct
5 Correct 31 ms 50040 KB Output is correct
6 Correct 35 ms 50128 KB Output is correct
7 Correct 33 ms 50048 KB Output is correct
8 Correct 32 ms 50048 KB Output is correct
9 Correct 33 ms 50040 KB Output is correct
10 Correct 31 ms 50040 KB Output is correct
11 Correct 32 ms 50048 KB Output is correct
12 Correct 32 ms 50048 KB Output is correct
13 Correct 32 ms 50048 KB Output is correct
14 Incorrect 32 ms 50048 KB Output isn't correct
15 Halted 0 ms 0 KB -