Submission #519044

#	Time	Username	Problem	Language	Result	Execution time	Memory
519044		fatemetmhr	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	572 ms	116824 KiB

constellation3

//  ~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 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65