oj.uz

답안 #519044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
519044 2022-01-25T12:52:26 Z fatemetmhr 별자리 3 (JOI20_constellation3) C++17
100 / 100
 572 ms 116824 KB 
//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int lg    =  18;
const ll  inf   =  2e18;

ll dp[maxn5], sum[maxn5];
ll lazy[maxnt];
pair <int, int> mx[lg][maxn5];
vector <int> adj[maxn5];
int st[maxn5], ft[maxn5], n, mxx[lg][maxn5];
int ti = -1, a[maxn5], par[lg][maxn5];
vector <pair<int, ll>> av[maxn5];

inline void add(int l, int r, int lq, int rq, ll val, int v){
	if(rq <= l || r <= lq)
		return;
	if(lq <= l && r <= rq){
		lazy[v] += val;
		return;
	}
	int mid = (l + r) >> 1;
	add(l, mid, lq, rq, val, v * 2);
	add(mid, r, lq, rq, val, v * 2 + 1);
	return;
}

inline ll get(int l, int r, int ind, int v){
	if(r - l == 1)
		return lazy[v];
	int mid = (l + r) >> 1;
	if(ind < mid)
		return lazy[v] + get(l, mid, ind, v * 2);
	return lazy[v] + get(mid, r, ind, v * 2 + 1);
}

inline int get_max(int l, int r){
	int k = 0;
	while((1 << (k + 1)) <= r - l + 1)
		k++;
	return max(mx[k][l], mx[k][r - (1 << k) + 1]).se;
}

inline int make_tree(int l, int r, int pa){
	int p = get_max(l, r - 1);
	par[0][p] = pa;
	if(p > l)
		adj[p].pb(make_tree(l, p, p));
	if(p + 1 < r)
		adj[p].pb(make_tree(p + 1, r, p));
	return p;
}

inline void dfs(int v){
	st[v] = ++ti;
	for(auto u : adj[v]){
		dfs(u);
		sum[v] += dp[u];
	}
	ft[v] = ti;
	dp[v] = sum[v];
	for(auto [u, c] : av[v]){
		if(u == v){
			dp[v] = max(dp[v], c + sum[v]);
			continue;
		}
		int z = adj[v][0];
		if(ft[z] < ft[u])
			z = adj[v][1];
		dp[v] = max(dp[v], c + sum[v] - dp[z] + get(0, n, st[u], 1));
		//cout << "hey! " << v << ' ' << dp[v] << ' ' << u << ' ' << z << ' ' << c << ' ' << get(0, n, st[u], 1) << '\n';
	}
	for(auto u : adj[v]){
		add(0, n, st[u], ft[u] + 1, sum[v] - dp[u], 1);
	}
	add(0, n, st[v], st[v] + 1, sum[v], 1);
	//cout << v << ' ' << dp[v] << '\n';
	return;
}

inline void dfs_lca(int v){
	if(par[0][v] != -1)
		mxx[0][v] = max(a[v], a[par[0][v]]);
	for(int i = 1; i < lg && par[i - 1][v] != -1; i++){
		par[i][v] = par[i - 1][par[i - 1][v]];
		mxx[i][v] = max(mxx[i - 1][v], mxx[i - 1][par[i - 1][v]]);
	}
	for(auto u : adj[v])
		dfs_lca(u);
	return;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		mx[0][i] = {a[i], i};
	}
	
		
	for(int i = 0; i < lg; i++) for(int j = 0; j < n; j++)
		par[i][j] = -1;

	for(int i = 1; i < lg; i++) for(int j = 0; j + (1 << i) - 1 < n; j++)
		mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
	int r = make_tree(0, n, -1);

	dfs_lca(r);
	
	int m; cin >> m;
	ll summ = 0;
	for(int i = 0; i < m; i++){
		int x, y, c; cin >> x >> y >> c;
		x--;
		int v = x;
		for(int i = lg - 1; i >= 0; i--) if(par[i][v] != -1 && mxx[i][v] < y){
			//cout << "ahaaa " << i << ' '<< v << ' '<< mxx[i][v] << ' ' << par[i][v] << '\n';
			v = par[i][v];
		}
		av[v].pb({x, c});
		summ += c;
		//cout << "aha " << x << ' ' << y << ' ' << v << ' ' << c << '\n';
	}
	dfs(r);
	cout << summ - dp[r] << endl;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9932 KB Output is correct
2 Correct 5 ms 9932 KB Output is correct
3 Correct 5 ms 9984 KB Output is correct
4 Correct 6 ms 9932 KB Output is correct
5 Correct 7 ms 9984 KB Output is correct
6 Correct 6 ms 9932 KB Output is correct
7 Correct 7 ms 9932 KB Output is correct
8 Correct 5 ms 9932 KB Output is correct
9 Correct 5 ms 9936 KB Output is correct
10 Correct 6 ms 10060 KB Output is correct
11 Correct 5 ms 10060 KB Output is correct
12 Correct 5 ms 9932 KB Output is correct
13 Correct 7 ms 9932 KB Output is correct
14 Correct 7 ms 9984 KB Output is correct
15 Correct 7 ms 9932 KB Output is correct
16 Correct 6 ms 9980 KB Output is correct
17 Correct 6 ms 9932 KB Output is correct
18 Correct 7 ms 10012 KB Output is correct
19 Correct 6 ms 9932 KB Output is correct
20 Correct 6 ms 9976 KB Output is correct
21 Correct 8 ms 9980 KB Output is correct
22 Correct 7 ms 9984 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9932 KB Output is correct
2 Correct 5 ms 9932 KB Output is correct
3 Correct 5 ms 9984 KB Output is correct
4 Correct 6 ms 9932 KB Output is correct
5 Correct 7 ms 9984 KB Output is correct
6 Correct 6 ms 9932 KB Output is correct
7 Correct 7 ms 9932 KB Output is correct
8 Correct 5 ms 9932 KB Output is correct
9 Correct 5 ms 9936 KB Output is correct
10 Correct 6 ms 10060 KB Output is correct
11 Correct 5 ms 10060 KB Output is correct
12 Correct 5 ms 9932 KB Output is correct
13 Correct 7 ms 9932 KB Output is correct
14 Correct 7 ms 9984 KB Output is correct
15 Correct 7 ms 9932 KB Output is correct
16 Correct 6 ms 9980 KB Output is correct
17 Correct 6 ms 9932 KB Output is correct
18 Correct 7 ms 10012 KB Output is correct
19 Correct 6 ms 9932 KB Output is correct
20 Correct 6 ms 9976 KB Output is correct
21 Correct 8 ms 9980 KB Output is correct
22 Correct 7 ms 9984 KB Output is correct
23 Correct 7 ms 10388 KB Output is correct
24 Correct 7 ms 10444 KB Output is correct
25 Correct 7 ms 10444 KB Output is correct
26 Correct 7 ms 10504 KB Output is correct
27 Correct 9 ms 10504 KB Output is correct
28 Correct 7 ms 10444 KB Output is correct
29 Correct 7 ms 10444 KB Output is correct
30 Correct 7 ms 10444 KB Output is correct
31 Correct 7 ms 10444 KB Output is correct
32 Correct 7 ms 10628 KB Output is correct
33 Correct 8 ms 10632 KB Output is correct
34 Correct 8 ms 10572 KB Output is correct
35 Correct 8 ms 10572 KB Output is correct
36 Correct 8 ms 10700 KB Output is correct
37 Correct 7 ms 10760 KB Output is correct
38 Correct 7 ms 10828 KB Output is correct
39 Correct 7 ms 10500 KB Output is correct
40 Correct 7 ms 10700 KB Output is correct
41 Correct 8 ms 10444 KB Output is correct
42 Correct 7 ms 10444 KB Output is correct
43 Correct 7 ms 10700 KB Output is correct
44 Correct 7 ms 10444 KB Output is correct

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9932 KB Output is correct
2 Correct 5 ms 9932 KB Output is correct
3 Correct 5 ms 9984 KB Output is correct
4 Correct 6 ms 9932 KB Output is correct
5 Correct 7 ms 9984 KB Output is correct
6 Correct 6 ms 9932 KB Output is correct
7 Correct 7 ms 9932 KB Output is correct
8 Correct 5 ms 9932 KB Output is correct
9 Correct 5 ms 9936 KB Output is correct
10 Correct 6 ms 10060 KB Output is correct
11 Correct 5 ms 10060 KB Output is correct
12 Correct 5 ms 9932 KB Output is correct
13 Correct 7 ms 9932 KB Output is correct
14 Correct 7 ms 9984 KB Output is correct
15 Correct 7 ms 9932 KB Output is correct
16 Correct 6 ms 9980 KB Output is correct
17 Correct 6 ms 9932 KB Output is correct
18 Correct 7 ms 10012 KB Output is correct
19 Correct 6 ms 9932 KB Output is correct
20 Correct 6 ms 9976 KB Output is correct
21 Correct 8 ms 9980 KB Output is correct
22 Correct 7 ms 9984 KB Output is correct
23 Correct 7 ms 10388 KB Output is correct
24 Correct 7 ms 10444 KB Output is correct
25 Correct 7 ms 10444 KB Output is correct
26 Correct 7 ms 10504 KB Output is correct
27 Correct 9 ms 10504 KB Output is correct
28 Correct 7 ms 10444 KB Output is correct
29 Correct 7 ms 10444 KB Output is correct
30 Correct 7 ms 10444 KB Output is correct
31 Correct 7 ms 10444 KB Output is correct
32 Correct 7 ms 10628 KB Output is correct
33 Correct 8 ms 10632 KB Output is correct
34 Correct 8 ms 10572 KB Output is correct
35 Correct 8 ms 10572 KB Output is correct
36 Correct 8 ms 10700 KB Output is correct
37 Correct 7 ms 10760 KB Output is correct
38 Correct 7 ms 10828 KB Output is correct
39 Correct 7 ms 10500 KB Output is correct
40 Correct 7 ms 10700 KB Output is correct
41 Correct 8 ms 10444 KB Output is correct
42 Correct 7 ms 10444 KB Output is correct
43 Correct 7 ms 10700 KB Output is correct
44 Correct 7 ms 10444 KB Output is correct
45 Correct 290 ms 79392 KB Output is correct
46 Correct 268 ms 78328 KB Output is correct
47 Correct 287 ms 77600 KB Output is correct
48 Correct 279 ms 79028 KB Output is correct
49 Correct 267 ms 77032 KB Output is correct
50 Correct 268 ms 77080 KB Output is correct
51 Correct 280 ms 77104 KB Output is correct
52 Correct 286 ms 78708 KB Output is correct
53 Correct 275 ms 78544 KB Output is correct
54 Correct 536 ms 106060 KB Output is correct
55 Correct 572 ms 99012 KB Output is correct
56 Correct 500 ms 95216 KB Output is correct
57 Correct 502 ms 92480 KB Output is correct
58 Correct 374 ms 99244 KB Output is correct
59 Correct 388 ms 98920 KB Output is correct
60 Correct 200 ms 116824 KB Output is correct
61 Correct 288 ms 79152 KB Output is correct
62 Correct 527 ms 107080 KB Output is correct
63 Correct 292 ms 78820 KB Output is correct
64 Correct 282 ms 76896 KB Output is correct
65 Correct 545 ms 108216 KB Output is correct
66 Correct 298 ms 78100 KB Output is correct