oj.uz

Submission #212846

# Submission time Handle Problem Language Result Execution time Memory
212846 2020-03-24T11:58:17 Z sinatori Constellation 3 (JOI20_constellation3) C++14
0 / 100
 25 ms 32896 KB 
#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];
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];
queue<int> Q;

int hlnum[400010], hlseg[400010], hltop[400010], hlpar[400010];

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;
	}
}

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);
	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

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 32768 KB Output is correct
2 Correct 24 ms 32768 KB Output is correct
3 Correct 25 ms 32768 KB Output is correct
4 Correct 25 ms 32768 KB Output is correct
5 Correct 25 ms 32768 KB Output is correct
6 Correct 25 ms 32768 KB Output is correct
7 Correct 25 ms 32768 KB Output is correct
8 Correct 24 ms 32832 KB Output is correct
9 Correct 25 ms 32768 KB Output is correct
10 Correct 25 ms 32896 KB Output is correct
11 Correct 25 ms 32896 KB Output is correct
12 Correct 25 ms 32888 KB Output is correct
13 Correct 25 ms 32896 KB Output is correct
14 Incorrect 25 ms 32896 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 32768 KB Output is correct
2 Correct 24 ms 32768 KB Output is correct
3 Correct 25 ms 32768 KB Output is correct
4 Correct 25 ms 32768 KB Output is correct
5 Correct 25 ms 32768 KB Output is correct
6 Correct 25 ms 32768 KB Output is correct
7 Correct 25 ms 32768 KB Output is correct
8 Correct 24 ms 32832 KB Output is correct
9 Correct 25 ms 32768 KB Output is correct
10 Correct 25 ms 32896 KB Output is correct
11 Correct 25 ms 32896 KB Output is correct
12 Correct 25 ms 32888 KB Output is correct
13 Correct 25 ms 32896 KB Output is correct
14 Incorrect 25 ms 32896 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 32768 KB Output is correct
2 Correct 24 ms 32768 KB Output is correct
3 Correct 25 ms 32768 KB Output is correct
4 Correct 25 ms 32768 KB Output is correct
5 Correct 25 ms 32768 KB Output is correct
6 Correct 25 ms 32768 KB Output is correct
7 Correct 25 ms 32768 KB Output is correct
8 Correct 24 ms 32832 KB Output is correct
9 Correct 25 ms 32768 KB Output is correct
10 Correct 25 ms 32896 KB Output is correct
11 Correct 25 ms 32896 KB Output is correct
12 Correct 25 ms 32888 KB Output is correct
13 Correct 25 ms 32896 KB Output is correct
14 Incorrect 25 ms 32896 KB Output isn't correct
15 Halted 0 ms 0 KB -