oj.uz

답안 #212854

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
212854 2020-03-24T12:12:40 Z sinatori 별자리 3 (JOI20_constellation3) C++14
0 / 100
 43 ms 68864 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;

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 < 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[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;
	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:245:6: warning: unused variable 'bef' [-Wunused-variable]
  int bef = 0;
      ^~~
constellation3.cpp:246:5: warning: unused variable 'ans' [-Wunused-variable]
  ll ans;
     ^~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 68856 KB Output is correct
2 Correct 41 ms 68856 KB Output is correct
3 Correct 40 ms 68856 KB Output is correct
4 Correct 40 ms 68864 KB Output is correct
5 Correct 40 ms 68856 KB Output is correct
6 Correct 41 ms 68864 KB Output is correct
7 Correct 40 ms 68864 KB Output is correct
8 Correct 41 ms 68864 KB Output is correct
9 Correct 41 ms 68856 KB Output is correct
10 Correct 39 ms 68856 KB Output is correct
11 Correct 42 ms 68856 KB Output is correct
12 Correct 40 ms 68856 KB Output is correct
13 Correct 39 ms 68864 KB Output is correct
14 Incorrect 39 ms 68856 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 68856 KB Output is correct
2 Correct 41 ms 68856 KB Output is correct
3 Correct 40 ms 68856 KB Output is correct
4 Correct 40 ms 68864 KB Output is correct
5 Correct 40 ms 68856 KB Output is correct
6 Correct 41 ms 68864 KB Output is correct
7 Correct 40 ms 68864 KB Output is correct
8 Correct 41 ms 68864 KB Output is correct
9 Correct 41 ms 68856 KB Output is correct
10 Correct 39 ms 68856 KB Output is correct
11 Correct 42 ms 68856 KB Output is correct
12 Correct 40 ms 68856 KB Output is correct
13 Correct 39 ms 68864 KB Output is correct
14 Incorrect 39 ms 68856 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 68856 KB Output is correct
2 Correct 41 ms 68856 KB Output is correct
3 Correct 40 ms 68856 KB Output is correct
4 Correct 40 ms 68864 KB Output is correct
5 Correct 40 ms 68856 KB Output is correct
6 Correct 41 ms 68864 KB Output is correct
7 Correct 40 ms 68864 KB Output is correct
8 Correct 41 ms 68864 KB Output is correct
9 Correct 41 ms 68856 KB Output is correct
10 Correct 39 ms 68856 KB Output is correct
11 Correct 42 ms 68856 KB Output is correct
12 Correct 40 ms 68856 KB Output is correct
13 Correct 39 ms 68864 KB Output is correct
14 Incorrect 39 ms 68856 KB Output isn't correct
15 Halted 0 ms 0 KB -