Submission #217005

#	Time	Username	Problem	Language	Result	Execution time	Memory
217005		abacaba	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	300 ms	39160 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
 
#define f first
#define se second
#define pb push_back
#define int long long
#define pii pair<int, int>

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> inline T range(T l, T r) {
	return uniform_int_distribution <T>(l, r)(rng);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}
 
const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 2e5 + 15;
int n, m, a[N];

struct fenw {
	int t[N];
	inline void inc(int i, int val) {
		for(; i <= n; i = (i | (i + 1)))
			t[i] += val;
	}
	inline int get(int i) {
		int res = 0;
		for(; i >= 1; i = (i & (i + 1)) - 1)
			res += t[i];
		return res;
	}
	inline void add(int l, int r, int x) {
		inc(l, x);
		inc(r + 1, -x);
	}
} t;

struct dsu {
	int p[N], sz[N], dp[N], ext[N], l[N], r[N];
	inline void init() {
		for(int i = 0; i < N; ++i)
			p[i] = i, sz[i] = 1, dp[i] = 0, ext[i] = 0, l[i] = r[i] = i;
	}
	int find(int v) {
		if(v == p[v])
			return v;
		return p[v] = find(p[v]);
	}
	inline void unio(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			if(sz[a] < sz[b])
				swap(a, b);

			t.add(l[b], r[b], dp[a] + ext[a]);
			t.add(l[a], r[a], dp[b] + ext[b]);

			Min(l[a], l[b]);
			Max(r[a], r[b]);

			dp[a] += ext[a] + ext[b] + dp[b];
			ext[a] = ext[b] = 0;

			p[b] = a;
			sz[a] += sz[b];
		}
	}
} st;


vector <pii> star[N];
vector <int> building[N];
int sum;

main() {
	st.init();
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		building[a[i]].pb(i);
	}
	cin >> m;
	for(int i = 1; i <= m; ++i) {
		int x, y, c;
		cin >> x >> y >> c;
		star[y].pb({x, c});
		sum += c;
	}
	for(int y = 1; y <= n; ++y) {
		for(pii x : star[y]) {
			int p = st.find(x.f);
			Max(st.ext[p], t.get(x.f) + x.se - st.dp[p]);
		}
		for(int x : building[y]) {
			if(x > 1 && a[x - 1] <= y)
				st.unio(x-1, x);
			if(x < n && a[x + 1] <= y)
				st.unio(x+1, x);
		}
	}
	for(int i = 2; i <= n; ++i)
		st.unio(i, i - 1);
	cout << sum - st.dp[st.find(1)] - st.ext[st.find(1)] << endl;
	return 0;
}

Compilation message (stderr)

constellation3.cpp:85:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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