Submission #212692

#	Time	Username	Problem	Language	Result	Execution time	Memory
212692		PinkRabbit	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	723 ms	99064 KiB

constellation3

#include <cstdio>
#include <algorithm>
#include <vector>

typedef long long LL;
const int MN = 200005, MM = 200005, MS = 4000005;

int N, A[MN], Root;
std::vector<int> G[MN];

void BuildCartesianTree() {
	static int stk[MN], tp, x;
	auto Add = [](int u, int v) {
		if (v) G[u].push_back(v);
	};
	for (int i = 1; i <= N; ++i) {
		for (x = 0; tp && A[stk[tp]] < A[i]; --tp)
			Add(stk[tp], x), x = stk[tp];
		Add(i, x), stk[++tp] = i;
	}
	for (x = 0; tp; --tp)
		Add(stk[tp], x), x = stk[tp];
	Root = x;
}

int dep[MN], par[MN][18];
void DFS(int u, int pa) {
	dep[u] = dep[par[u][0] = pa] + 1;
	for (int j = 0; 2 << j < dep[u]; ++j)
		par[u][j + 1] = par[par[u][j]][j];
	for (int v : G[u]) DFS(v, u);
}

int M, w[MM];
std::vector<int> V0[MN], V1[MN];

#define li lc[i]
#define ri rc[i]
#define mid ((l + r) >> 1)
#define ls li, l, mid
#define rs ri, mid + 1, r
int lc[MS], rc[MS], cnt;
LL tg[MS];
inline void P(int i, LL x) { if (i) tg[i] += x; }
inline void Pushdown(int i) { if (tg[i]) P(li, tg[i]), P(ri, tg[i]), tg[i] = 0; }
void Mdf(int &i, int l, int r, int p, LL x) {
	if (!i) i = ++cnt;
	if (l == r) return tg[i] = x, void();
	Pushdown(i), p <= mid ? Mdf(ls, p, x) : Mdf(rs, p, x);
}
LL Qur(int i, int l, int r, int p) {
	if (l == r) return tg[i];
	Pushdown(i);
	return p <= mid ? Qur(ls, p) : Qur(rs, p);
}
void Merge(int &i, int l, int r, int i2) {
	if (!i2) return ;
	if (!i) return i = i2, void();
	Pushdown(i), Pushdown(i2);
	Merge(ls, lc[i2]), Merge(rs, rc[i2]);
}

int rt[MN]; LL dp[MN], Sum;
void Solve(int u) {
	for (int v : G[u]) Solve(v), dp[u] += dp[v];
	for (int v : G[u]) P(rt[v], dp[u] - dp[v]), Merge(rt[u], 1, M, rt[v]);
	for (int i : V0[u]) Mdf(rt[u], 1, M, i, w[i] + dp[u]);
	for (int i : V1[u]) dp[u] = std::max(dp[u], Qur(rt[u], 1, M, i));
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
	BuildCartesianTree();
	DFS(Root, 0);
	A[0] = N;
	scanf("%d", &M);
	for (int i = 1; i <= M; ++i) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &w[i]), z = x;
		for (int j = 17; j >= 0; --j)
			if (y > A[par[z][j]]) z = par[z][j];
		V0[x].push_back(i);
		V1[z].push_back(i);
		Sum += w[i];
	}
	Solve(Root);
	printf("%lld\n", Sum - dp[Root]);
	return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
constellation3.cpp:73:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
                               ~~~~~^~~~~~~~~~~~~
constellation3.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &M);
  ~~~~~^~~~~~~~~~
constellation3.cpp:80:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &w[i]), z = x;
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

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