Submission #521611

#	Time	Username	Problem	Language	Result	Execution time	Memory
521611		eecs	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	506 ms	164596 KiB

worst_reporter2

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

typedef long long ll;
const int maxn = 200010;
int n, tot, a[maxn], h[maxn], c[maxn], vis[maxn], foo[maxn], rt[maxn];
ll all, ans;
vector<int> G[maxn], bel[maxn];
struct node { int l, r; ll mx, tag; } t[maxn * 100];
unordered_map<int, ll> mp;

#define mid (l + r >> 1)
inline void maintain(int k) {
	t[k].mx = max(t[t[k].l].mx, t[t[k].r].mx);
}

void pushdown(int k) {
	if (!t[k].tag) return;
	if (!t[k].l) t[k].l = ++tot;
	t[t[k].l].tag += t[k].tag, t[t[k].l].mx += t[k].tag;
	if (!t[k].r) t[k].r = ++tot;
	t[t[k].r].tag += t[k].tag, t[t[k].r].mx += t[k].tag;
	t[k].tag = 0;
}

int merge(int k1, int k2, int l, int r, ll mx1, ll mx2) {
	if (!k1 && !k2) return 0;
	if (!k2) { t[k1].tag += mx2, t[k1].mx += mx2; return k1; }
	if (!k1) { t[k2].tag += mx1, t[k2].mx += mx1; return k2; }
	if (l == r) {
		t[k1].mx = max({t[k1].mx + mx2, t[k2].mx + mx1, t[k1].mx + t[k2].mx});
		return k1;
	}
	if (!t[k1].l && !t[k1].r) {
		mx1 = max(mx1, t[k1].mx);
		t[k2].tag += mx1, t[k2].mx += mx1;
		return k2;
	}
	if (!t[k2].l && !t[k2].r) {
		mx2 = max(mx2, t[k2].mx);
		t[k1].tag += mx2, t[k1].mx += mx2;
		return k1;
	}
	pushdown(k1), pushdown(k2);
	t[k1].l = merge(t[k1].l, t[k2].l, l, mid, max(mx1, t[t[k1].r].mx) + t[k1].tag,
		max(mx2, t[t[k2].r].mx) + t[k2].tag);
	t[k1].r = merge(t[k1].r, t[k2].r, mid + 1, r, mx1, mx2);
	maintain(k1); return k1;
}

void modify(int &k, int l, int r, int p, ll v) {
	if (!k) k = ++tot;
	if (l == r) { t[k].mx = max(t[k].mx, v); return; }
	pushdown(k);
	if (mid >= p) modify(t[k].l, l, mid, p, v);
	else modify(t[k].r, mid + 1, r, p, v);
	maintain(k);
}

ll query(int k, int l, int r, int ql, int qr) {
	if (!k || l >= ql && r <= qr) return t[k].mx;
	pushdown(k);
	ll ans = 0;
	if (mid >= ql) ans = query(t[k].l, l, mid, ql, qr);
	if (mid < qr) ans = max(ans, query(t[k].r, mid + 1, r, ql, qr));
	return ans;
}

int find(int x) {
	return x == foo[x] ? x : foo[x] = find(foo[x]);
}

int main() {
	scanf("%d", &n);
	vector<int> V;
	iota(foo + 1, foo + n + 1, 1);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d %d", &a[i], &h[i], &c[i]);
		all += c[i], V.push_back(h[i]);
		foo[find(i)] = find(a[i]);
	}
	sort(V.begin(), V.end());
	V.resize(unique(V.begin(), V.end()) - V.begin());
	for (int i = 1; i <= n; i++) {
		h[i] = lower_bound(V.begin(), V.end(), h[i]) - V.begin() + 1;
		bel[find(i)].push_back(i);
	}
	for (int i = 1; i <= n; i++) if (i == find(i)) {
		int tim = 0, tr = 0;
		V.clear(), mp.clear();
		int l, r;
		for (int j = i; ; j = a[j]) {
			if (vis[j]) { l = vis[j], r = tim; break; }
			vis[j] = ++tim;
		}
		for (int j : bel[i]) {
			if (vis[j] >= l && vis[j] <= r) V.push_back(j), mp[h[j]] += c[j];
			else G[a[j]].push_back(j);
		}
		function<void(int)> dfs = [&](int v) {
			for (int u : G[v]) {
				dfs(u), rt[v] = ::merge(rt[v], rt[u], 1, n, 0, 0);
			}
			modify(rt[v], 1, n, h[v], c[v] + query(rt[v], 1, n, h[v], n));
		};
		for (int j : V) for (int k : G[j]) {
			dfs(k), tr = ::merge(tr, rt[k], 1, n, 0, 0);
		}
		ll bar = t[tr].mx;
		for (auto p : mp) {
			bar = max(bar, p.second + query(tr, 1, n, p.first, n));
		}
		ans += bar;
	}
	printf("%lld\n", all - ans);
	return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int merge(int, int, int, int, ll, ll)':
worst_reporter2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 | #define mid (l + r >> 1)
      |              ~~^~~
worst_reporter2.cpp:45:39: note: in expansion of macro 'mid'
   45 |  t[k1].l = merge(t[k1].l, t[k2].l, l, mid, max(mx1, t[t[k1].r].mx) + t[k1].tag,
      |                                       ^~~
worst_reporter2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 | #define mid (l + r >> 1)
      |              ~~^~~
worst_reporter2.cpp:47:36: note: in expansion of macro 'mid'
   47 |  t[k1].r = merge(t[k1].r, t[k2].r, mid + 1, r, mx1, mx2);
      |                                    ^~~
worst_reporter2.cpp: In function 'void modify(int&, int, int, int, ll)':
worst_reporter2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 | #define mid (l + r >> 1)
      |              ~~^~~
worst_reporter2.cpp:55:6: note: in expansion of macro 'mid'
   55 |  if (mid >= p) modify(t[k].l, l, mid, p, v);
      |      ^~~
worst_reporter2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 | #define mid (l + r >> 1)
      |              ~~^~~
worst_reporter2.cpp:55:34: note: in expansion of macro 'mid'
   55 |  if (mid >= p) modify(t[k].l, l, mid, p, v);
      |                                  ^~~
worst_reporter2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 | #define mid (l + r >> 1)
      |              ~~^~~
worst_reporter2.cpp:56:22: note: in expansion of macro 'mid'
   56 |  else modify(t[k].r, mid + 1, r, p, v);
      |                      ^~~
worst_reporter2.cpp: In function 'll query(int, int, int, int, int)':
worst_reporter2.cpp:61:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   61 |  if (!k || l >= ql && r <= qr) return t[k].mx;
      |            ~~~~~~~~^~~~~~~~~~
worst_reporter2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 | #define mid (l + r >> 1)
      |              ~~^~~
worst_reporter2.cpp:64:6: note: in expansion of macro 'mid'
   64 |  if (mid >= ql) ans = query(t[k].l, l, mid, ql, qr);
      |      ^~~
worst_reporter2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 | #define mid (l + r >> 1)
      |              ~~^~~
worst_reporter2.cpp:64:40: note: in expansion of macro 'mid'
   64 |  if (mid >= ql) ans = query(t[k].l, l, mid, ql, qr);
      |                                        ^~~
worst_reporter2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 | #define mid (l + r >> 1)
      |              ~~^~~
worst_reporter2.cpp:65:6: note: in expansion of macro 'mid'
   65 |  if (mid < qr) ans = max(ans, query(t[k].r, mid + 1, r, ql, qr));
      |      ^~~
worst_reporter2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 | #define mid (l + r >> 1)
      |              ~~^~~
worst_reporter2.cpp:65:45: note: in expansion of macro 'mid'
   65 |  if (mid < qr) ans = max(ans, query(t[k].r, mid + 1, r, ql, qr));
      |                                             ^~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
worst_reporter2.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d %d %d", &a[i], &h[i], &c[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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