Submission #1153090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153090		AmirAli_H1	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	287 ms	68860 KiB

constellation3

// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (1 << 18) + 4;
const ll oo = 1e18 + 4;

int n, m; pll A[maxn];
vector<int> adj[maxn]; int L[maxn], R[maxn];
set<pll> gooni[maxn]; ll val[maxn];

void addx(int i, pll x) {
	gooni[i].insert(x);
	while (true) {
		auto it = gooni[i].lower_bound(x);
		if (it == gooni[i].begin() || it == gooni[i].end()) break;
		pll x2 = (*it); it--; pll x1 = (*it);
		if (x1.F == x2.F) {
			gooni[i].erase(x1);
		}
		else if (x1.S >= x2.S) {
			gooni[i].erase(x2);
		}
		else break;
	}
	while (true) {
		auto it = gooni[i].upper_bound(x);
		if (it == gooni[i].begin() || it == gooni[i].end()) break;
		pll x2 = (*it); it--; pll x1 = (*it);
		if (x1.F == x2.F) {
			gooni[i].erase(x1);
		}
		else if (x1.S >= x2.S) {
			gooni[i].erase(x2);
		}
		else break;
	}
}

ll get_val(int i, ll x) {
	auto it = gooni[i].upper_bound(Mp(x, oo));
	if (it == gooni[i].begin()) return val[i];
	it--; ll R = (*it).S;
	return R + val[i];
}

void sack(int v) {
	for (int u : adj[v]) sack(u);
	ll sm = 0;
	for (int u : adj[v]) {
		sm += get_val(u, A[v].F);
	}
	val[v] += sm;
	for (int u : adj[v]) {
		val[u] += (sm - get_val(u, A[v].F));
	}
	for (int u : adj[v]) {
		if (len(gooni[u]) > len(gooni[v])) {
			gooni[v].swap(gooni[u]);
			swap(val[v], val[u]);
		}
		for (auto f : gooni[u]) {
			pll x = Mp(f.F, f.S + val[u] - val[v]);
			addx(v, x);
		}
		gooni[u].clear();
	}
}

void solve() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i].F;
		A[i].F--; A[i].S = i;
	}
	cin >> m; ll sm = 0;
	for (int i = 0; i < m; i++) {
		int x, y; ll valx;
		cin >> x >> y >> valx; sm += valx;
		x--; y--; addx(x, Mp(y, valx));
	}

	for (int i = 0; i < n; i++) {
		for (L[i] = i - 1; L[i] != -1 && A[i] >= A[L[i]]; L[i] = L[L[i]]);
	}
	for (int i = n - 1; i >= 0; i--) {
		for (R[i] = i + 1; R[i] != n && A[i] >= A[R[i]]; R[i] = R[R[i]]);
	}
	int v = -1;
	for (int i = 0; i < n; i++) {
		if (L[i] == -1 && R[i] == n) v = i;
		else if (L[i] == -1) {
			adj[R[i]].pb(i);
		}
		else if (R[i] == n) {
			adj[L[i]].pb(i);
		}
		else {
			if (A[R[i]] < A[L[i]]) adj[R[i]].pb(i);
			else adj[L[i]].pb(i);
		}
	}
	sack(v);
	
	cout << sm - get_val(v, oo) << endl;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int T = 1;
	while (T--) {
		solve();
	}
	
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65