oj.uz

Submission #628234

# Submission time Handle Problem Language Result Execution time Memory
628234 2022-08-13T08:40:31 Z sysia Constellation 3 (JOI20_constellation3) C++17
100 / 100
 459 ms 108472 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
const int oo = 1e18, K = 30;

struct star{
	int x, y, c;
	void read(){
		cin >> x >> y >> c;
	}
};

struct TreeMax{
	vector<pair<int, int>>tab;
	int size = 1;

	TreeMax(int n){
		while (size < n) size*=2;
		tab.assign(2*size, {-oo, -oo});
	}

	void update(int x, pair<int, int> v){
		x += size;
		tab[x] = v;
		while (x){
			x/=2;
			tab[x] = max(tab[2*x], tab[2*x+1]);
		}
	}

	int query(int l, int r){
		pair<int, int>ans = {-oo, -oo};
		l = l+size-1;
		r = r+size+1;
		while (r-l>1){
			if (!(l&1)) ans = max(ans, tab[l+1]);
			if (r&1) ans = max(ans, tab[r-1]);
			l/=2;r/=2;
		}
		return ans.second;
	}
};

struct TreeSum{
	vector<int>tab;
	int size = 1;

	TreeSum(int n){
		while (size < n) size*=2;
		tab.resize(2*size);
	}

	void update(int x, int v){
		x += size;
		tab[x] += v;
		while (x){
			x/=2;
			tab[x] = tab[2*x] + tab[2*x+1];
		}
	}

	int query(int l, int r){
		int ans = 0;
		l = l+size-1;
		r = r+size+1;
		while (r-l>1){
			if (!(l&1)) ans += tab[l+1];
			if (r&1) ans += tab[r-1];
			l/=2;r/=2;
		}
		return ans;
	}
};

void solve(){
	int n; cin >> n;
	vector<int>a(n+1);
	for (int i = 1; i<=n; i++) cin >> a[i];

	int m; cin >> m;
	vector<star>b(m);
	int s = 0;
	for (auto &x: b) {
		x.read();
		s += x.c;
	}
	sort(b.begin(), b.end(), [](auto x, auto y){return x.x < y.x;});
	vector<vector<int>>g(n+1);
	vector<vector<int>>paths(n+1);
	int c = 0;
	TreeMax smax(n+1);
	for (int i = 1; i<=n; i++) smax.update(i, {a[i], i});
	TreeMax gw(m+1);
	for (int i = 0; i<m; i++) gw.update(i, {b[i].y, i});
	vector<int>kon(n+1);

	function<void(int, int, int)>rek = [&](int l, int r, int pa){
		if (l > r) return;
		c++;
		if (pa != -1){
			g[pa].emplace_back(c);
			// debug(pa, c);
		}
		int h = smax.query(l, r);
		kon[h] = c; 
		// debug(l, r, h, a[h]);
		
		int L = 0, R = m-1, ll = oo, rr = -oo;
		while (R >= L){
			int mid = (L+R)/2;
			if (b[mid].x >= l){
				ll = mid;
				R = mid-1;
			} else L = mid+1;
		}

		L = 0, R = m-1;
		while (R >= L){
			int mid = (L+R)/2;
			if (b[mid].x <= r){
				rr = mid;
				L = mid+1;
			} else {
				R = mid-1;
			}
		}
		
		if (ll <= rr){
			// debug(l, r, ll, rr);
			while (1){
				int x = gw.query(ll, rr);
				if (x == -oo || b[x].y <= a[h]) break;
				paths[c].emplace_back(x);
				gw.update(x, {-oo, -oo});		
			}
		}
		
		int p = c;
		rek(l, h-1, p);
		rek(h+1, r, p);
	};

	rek(1, n, -1);

	vector<int>dp(n+1), ord, pre(n+1), post(n+1), par(n+1, 1);

	function<void(int)>dfs = [&](int v){
		pre[v] = ord.size();
		ord.emplace_back(v);
		for (auto x: g[v]) {
			par[x] = v;
			dfs(x);
		}
		post[v] = ord.size();
		ord.emplace_back(v);
		
	};

	// for (int i = 1; i<=n; i++){
	// 	for (auto x: paths[i]){
	// 		cerr << i << " " << kon[b[x].x] << " " << b[x].c << "\n";
	// 	}
	// }
	dfs(1);

	TreeSum seg(2*n+21);//.37
	TreeSum dp_sum(2*n+21);
	// debug(kon);

	auto get_sum = [&](int a, int b){
		// debug(a, b);
		int ans = seg.query(0, pre[b]) - (a != 1 ? seg.query(0, pre[a]-1) : 0);
		ans -= (dp_sum.query(0, pre[b]) - (a != 1 ? dp_sum.query(0, pre[a]-1) : 0));
		return ans;
	};

	function<void(int, int)>DFS = [&](int v, int pa){
		for (auto x: g[v]) {
			DFS(x, v);
			dp[v] += dp[x];
		}
		for (auto x: paths[v]) dp[v] = max(dp[v], get_sum(v, kon[b[x].x]) + b[x].c);
		if (pa != -1){
			seg.update(pre[pa], dp[v]);
			seg.update(post[pa], -dp[v]);
		}
		dp_sum.update(pre[v], dp[v]);
		dp_sum.update(post[v], -dp[v]);
	};

	DFS(1, -1);
	// debug(dp);
	cout << s-dp[1] << "\n";
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solve();
	
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 452 KB Output is correct
18 Correct 1 ms 452 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 340 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 452 KB Output is correct
18 Correct 1 ms 452 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 3 ms 920 KB Output is correct
24 Correct 3 ms 980 KB Output is correct
25 Correct 3 ms 980 KB Output is correct
26 Correct 3 ms 980 KB Output is correct
27 Correct 3 ms 980 KB Output is correct
28 Correct 3 ms 900 KB Output is correct
29 Correct 3 ms 980 KB Output is correct
30 Correct 4 ms 980 KB Output is correct
31 Correct 3 ms 980 KB Output is correct
32 Correct 3 ms 1108 KB Output is correct
33 Correct 3 ms 1108 KB Output is correct
34 Correct 4 ms 1108 KB Output is correct
35 Correct 3 ms 1044 KB Output is correct
36 Correct 3 ms 1108 KB Output is correct
37 Correct 3 ms 1108 KB Output is correct
38 Correct 3 ms 1236 KB Output is correct
39 Correct 3 ms 980 KB Output is correct
40 Correct 4 ms 1236 KB Output is correct
41 Correct 4 ms 980 KB Output is correct
42 Correct 3 ms 980 KB Output is correct
43 Correct 3 ms 1236 KB Output is correct
44 Correct 3 ms 976 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 452 KB Output is correct
18 Correct 1 ms 452 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 3 ms 920 KB Output is correct
24 Correct 3 ms 980 KB Output is correct
25 Correct 3 ms 980 KB Output is correct
26 Correct 3 ms 980 KB Output is correct
27 Correct 3 ms 980 KB Output is correct
28 Correct 3 ms 900 KB Output is correct
29 Correct 3 ms 980 KB Output is correct
30 Correct 4 ms 980 KB Output is correct
31 Correct 3 ms 980 KB Output is correct
32 Correct 3 ms 1108 KB Output is correct
33 Correct 3 ms 1108 KB Output is correct
34 Correct 4 ms 1108 KB Output is correct
35 Correct 3 ms 1044 KB Output is correct
36 Correct 3 ms 1108 KB Output is correct
37 Correct 3 ms 1108 KB Output is correct
38 Correct 3 ms 1236 KB Output is correct
39 Correct 3 ms 980 KB Output is correct
40 Correct 4 ms 1236 KB Output is correct
41 Correct 4 ms 980 KB Output is correct
42 Correct 3 ms 980 KB Output is correct
43 Correct 3 ms 1236 KB Output is correct
44 Correct 3 ms 976 KB Output is correct
45 Correct 312 ms 73052 KB Output is correct
46 Correct 304 ms 72532 KB Output is correct
47 Correct 308 ms 72500 KB Output is correct
48 Correct 302 ms 72644 KB Output is correct
49 Correct 315 ms 71996 KB Output is correct
50 Correct 311 ms 71868 KB Output is correct
51 Correct 311 ms 72060 KB Output is correct
52 Correct 304 ms 72912 KB Output is correct
53 Correct 310 ms 72592 KB Output is correct
54 Correct 444 ms 95604 KB Output is correct
55 Correct 459 ms 88752 KB Output is correct
56 Correct 417 ms 84644 KB Output is correct
57 Correct 426 ms 82216 KB Output is correct
58 Correct 371 ms 88336 KB Output is correct
59 Correct 380 ms 88672 KB Output is correct
60 Correct 374 ms 108472 KB Output is correct
61 Correct 329 ms 72196 KB Output is correct
62 Correct 453 ms 98680 KB Output is correct
63 Correct 311 ms 71796 KB Output is correct
64 Correct 298 ms 70924 KB Output is correct
65 Correct 450 ms 99004 KB Output is correct
66 Correct 308 ms 71448 KB Output is correct