제출 #531185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531185		blue	별자리 3 (JOI20_constellation3)	C++17	100 / 100	261 ms	32272 KiB

constellation3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
using ll = long long;
using vll = vector<ll>;

const int mx = 200'000;

int N, M;

vi occ[1 + mx];

vector<pii> stars[1 + mx];

vll bit(1 + mx);

void add(int i, ll v)
{
	for(int j = i; j <= N; j += j&-j)
		bit[j] += v;
}

ll prefsum(int i)
{
	ll res = 0;
	for(int j = i; j >= 1; j -= j&-j)
		res += bit[j];

	return res;
}

struct DSU
{
	vi par = vi(1 + mx);
	vi st = vi(1 + mx);
	vi l = vi(1 + mx);
	vi r = vi(1 + mx);
	vll dp = vll(1 + mx);

	DSU()
	{
		for(int i = 1; i <= N; i++)
		{
			par[i] = i;
			st[i] = 1;
			l[i] = r[i] = i;
			dp[i] = 0;
		}
	}

	int root(int u)
	{
		if(par[u] == u) return u;
		else return (par[u] = root(par[u]));
	}

	void join(int u, int v)
	{
		u = root(u);
		v = root(v);
		if(u == v) return;

		// cerr << "joining " << u << ' ' << v << '\n';
 
		if(st[u] < st[v]) swap(u, v);

		add(l[u], +dp[v]);
		add(r[u]+1, -dp[v]);
		// cerr << "  : " << dp[v] << '\n';
		// cerr << "adding dp " << v << " to " << l[u] << ' ' << r[u] << '\n';

		add(l[v], +dp[u]);
		add(r[v]+1, -dp[u]);

		// cerr << "  : " << dp[v] << '\n';
		// cerr << "adding dp " << u << " to " << l[v] << ' ' << r[v] << '\n';

		par[v] = u;
		st[u] += st[v];
		l[u] = min(l[u], l[v]);
		r[u] = max(r[u], r[v]);
		dp[u] += dp[v];
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	vi A(1 + N);

	for(int i = 1; i <= N; i++)
	{
		cin >> A[i];
		occ[A[i]].push_back(i);
	}

	cin >> M;

	ll tot = 0;

	for(int j = 1; j <= M; j++)
	{
		int x, y, c;
		cin >> x >> y >> c;

		tot += c;

		stars[y].push_back({x, c});
	}

	DSU dsu;

	for(int h = 1; h <= N; h++)
	{
		// cerr << "\n\n\n height = " << h << '\n';



		

		for(pii star : stars[h])
		{
			// cerr << "\n\n\n!!!\n";
			dsu.dp[dsu.root(star.first)] = max(dsu.dp[dsu.root(star.first)], prefsum(star.first) + star.second);
			
			// cerr << star.first << ' ' << star.second << " <> " << prefsum(star.first) << '\n';

			// cerr << dsu.root(star.first) << " : " << dsu.dp[dsu.root(star.first)] << '\n';
		}





		for(int i : occ[h])
		{
			if(1 <= i-1 && A[i-1] <= h)
				dsu.join(i-1, i);

			if(i+1 <= N && A[i+1] <= h)
				dsu.join(i, i+1);
		}
	}

	cout << tot - dsu.dp[dsu.root(1)] << '\n';
}

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