Submission #850562

#	Time	Username	Problem	Language	Result	Execution time	Memory
850562		b6e1	Closing Time (IOI23_closing)	C++17	75 / 100	179 ms	57792 KiB

closing

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll z[400005];
struct node {
	ll a, b;
	bool operator < (const node &z) const {
		return b < z.b;
	}
} c[400005];
namespace Cardboard_Box {
	int cnt, p[400005], q[400005];
	ll d[400005], nu[400005], su[400005];
	void add (int x, int v1, int v2) {
		while (x <= cnt) {
			nu[x] += v1, su[x] += v2;
			x += x & -x;
		}
	}
	int solve (int n, ll K, node *c, int m, ll *z) {
		cnt = 0;
		for (int i = 1; i <= m; i++) d[++cnt] = z[i];
		for (int i = 1; i <= n; i++) {
			d[++cnt] = c[i].a;
			d[++cnt] = c[i].b - c[i].a;
		}
		sort (c + 1, c + n + 1);
		sort (d + 1, d + cnt + 1);
		cnt = unique (d + 1, d + cnt + 1) - d - 1;
		int sum = 0;
		memset (nu, 0, cnt + 2 << 3);
		memset (su, 0, cnt + 2 << 3);
		for (int i = 1; i <= m; i++) {
			int pos = lower_bound (d + 1, d + cnt + 1, z[i]) - d;
			add (pos, 1, z[i]);
		}
		for (int i = 1; i <= n; i++) {
			p[i] = lower_bound (d + 1, d + cnt + 1, c[i].a) - d;
			q[i] = lower_bound (d + 1, d + cnt + 1, c[i].b - c[i].a) - d;
			add (p[i], 1, c[i].a);
		}
		ll ans = 0;
		for (int i = 0; i <= n; i++) {
			if (i) {
				add (p[i], -1, -c[i].a);
				add (q[i], 1, c[i].b - c[i].a);
				K -= c[i].a;
			}
			if (K < 0) break;
			ll p = 0, num = 0, sum = 0;
			for (int j = __lg (cnt); j >= 0; j--) {
				int np = p + (1 << j);
				if (np > cnt || sum + su[np] > K) continue;
				p = np, num += nu[p], sum += su[p];
			}
			if (p < cnt) num += (K - sum) / d[p + 1];
			ans = max (ans, num + i);
		}
		return ans;
	}
}
ll dx[400005], dy[400005];
vector<pair <int, int>> e[400005];
void dfs (int x, int fl, ll *d) {
	if (fl == -1) d[x] = 0;
	for (pair <int, int> t : e[x]) {
		int it = t.first;
		if (it == fl) continue;
		d[it] = d[x] + t.second;
		dfs (it, x, d);
	}
}
int max_score (int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
	for (int i = 0; i < N; i++) e[i].clear();
	for (int i = 0; i + 1 < N; i++) {
		e[U[i]].push_back ({V[i], W[i]});
		e[V[i]].push_back ({U[i], W[i]});
	}
	dfs (X, -1, dx), dfs (Y, -1, dy);
	vector<int> arr;
	for (int i = 0; i < N; i++) {
		arr.push_back (dx[i]);
		arr.push_back (dy[i]);
	}
	sort (arr.begin(), arr.end());
	int ans = 0;
	ll sum = 0;
	for (int i = 0; i < (int)arr.size(); i++) {
		if ((sum += arr[i]) > K) break;
		ans++;
	}
	int n = 0, m = 0, cnt = 0;
	for (int i = 0; i < N; i++) {
		int mn = min (dx[i], dy[i]);
		int mx = max (dx[i], dy[i]);
		if (dx[i] + dy[i] == dx[Y]) {
			cnt++, K -= mn;
			z[++ m] = mx - mn;
		} 
		else c[++ n] = {mn, mx};
	}
	if (K >= 0) ans = max (ans, cnt + Cardboard_Box::solve (n, K, c, m, z));
	return ans;
}

Compilation message (stderr)

closing.cpp: In function 'int Cardboard_Box::solve(int, long long int, node*, int, long long int*)':
closing.cpp:31:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   31 |   memset (nu, 0, cnt + 2 << 3);
      |                  ~~~~^~~
closing.cpp:32:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   32 |   memset (su, 0, cnt + 2 << 3);
      |                  ~~~~^~~
closing.cpp:30:7: warning: unused variable 'sum' [-Wunused-variable]
   30 |   int sum = 0;
      |       ^~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 17