Submission #1254509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254509		penguin133	Closing Time (IOI23_closing)	C++20	0 / 100	1096 ms	73896 KiB

closing

#include <bits/stdc++.h>
using namespace std;
#include "closing.h"
//#define int long long
using ll = long long;
#define pi pair<ll, ll>
#define pii pair<ll, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll e[200005];

struct node{
	int s, e, m;
	ll val, cnt;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m + 1, e);
		val = cnt = 0;
	}
	
	void upd(ll p, ll v){
		if(s == e){
			val += v;
			cnt += (v > 0 ? 1 : -1);
		}
		else{
			if(p <= m)l->upd(p, v);
			else r->upd(p, v);
		}
	}
	
	ll fd(ll x){
		if(s == e)return s;
		else if(l->val <= x)return r->fd(x - l->val);
		else return l->fd(x);
	}
	
	ll qry(int a, int b){
		if(a == s && b == e)return cnt;
		if(b <= m)return l->qry(a, b);
		if(a > m)return r->qry(a, b);
		else return l->qry(a, m) + r->qry(m + 1, b);
	}
	
	ll qv(int a, int b){
		if(a == s && b == e)return val;
		if(b <= m)return l->qv(a, b);
		if(a > m)return r->qv(a, b);
		else return l->qv(a, m) + r->qv(m + 1, b);
	}
}*root;

ll a[200005], b[200005], p[200005], vs[200005], pa[200005], pb[200005];
vector <pi> adj[200005];
vector <ll> dis;

ll f(int x){
	return lower_bound(dis.begin(), dis.end(), x) - dis.begin() + 1;
}

ll r(int x){
	if(x > (int)dis.size())return 1e18;
	return dis[x - 1];
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
	ll x = X, y = Y;
	vector <ll> v;
	for(int i = 0; i < N; i++)vs[i] = 0;
	for(int i = 0; i < N - 1; i++)e[i + 1] = W[i];
	for(int i = 1; i < N; i++)e[i] += e[i - 1];
	for(int i = 0; i < N; i++){
		a[i] = (i >= x ? e[i] - e[x] : e[x] - e[i]);
		b[i] = (i >= y ? e[i] - e[y] : e[y] - e[i]);
	}
	p[0] = max(a[0], b[0]);
	for(int i = 1; i < N; i++)p[i] = p[i - 1] + max(a[i], b[i]);
	pa[0] = a[0], pb[0] = b[0];
	for(int i = 1; i < N; i++)pa[i] = pa[i - 1] + a[i], pb[i] = pb[i - 1] + b[i];
	for(int i = 0; i < N; i++){
		//cerr << a[i] << ' ' << b[i] << ' ' << pa[i] << ' ' << pb[i] << ' ' << p[i] << '\n';
	}
	dis.clear();
	for(int i = 0; i < N; i++){
		dis.push_back(a[i]); dis.push_back(b[i]);
	}
	sort(dis.begin(), dis.end());
	dis.erase(unique(dis.begin(), dis.end()), dis.end());
	root = new node(0, (int)dis.size() + 5);
	for(int i = y + 1; i < N; i++)root->upd(f(b[i]), b[i]);
	ll ans = 0;
	for(int i = 0; i <= y; i++){
		for(int j = max(x, 1ll * i); j < N; j++){
			ll lol = (j - i + 1) * 2;
			ll cur = p[j] - (i == 0 ? 0 : p[i - 1]);
			if(j < y)cur += pb[y] - pb[j], lol += y - j;
			if(i > x)cur += pa[i - 1] - (x == 0 ? 0 : pa[x - 1]), lol += i - x;
			if(j > y)root->upd(f(b[j]), -b[j]);
			if(cur > K)continue;
			//cerr << j << ' ';
			int tmp = root->fd(K - cur), res = root->qv(0, tmp);
			//cerr << j << ' ' << tmp << ' ' << (int)dis.size() << ' ';
			ans = max(ans, lol + root->qry(0, tmp) + min((tmp == (int)dis.size() + 5? 0 : root->qry(tmp + 1, tmp + 1)), (K - cur - res) / r(tmp + 1)));
			//cerr << j << ' ';
		}
		
		for(int j = y + 1; j < N; j++)root->upd(f(b[j]), b[j]);
		if(i < x)root->upd(f(a[i]), a[i]);
	}
	for(int i = 0; i < N - 1; i++){
		adj[U[i]].push_back({V[i], W[i]});
		adj[V[i]].push_back({U[i], W[i]});
	}
	vs[X] = vs[Y] = 1;
	priority_queue <pi, vector <pi>, greater <pi> > pq;
	for(auto [i, j] : adj[X]){
		if(!vs[i])pq.push({j, i});
	}
	for(auto [i, j] : adj[Y]){
		if(!vs[i])pq.push({j, i});
	}
	ll ans2 = 2, cur1 = 0;
	while(!pq.empty()){
		ll t1 = pq.top().fi, t2 = pq.top().se; pq.pop();
		if(vs[t2])continue;
		if(cur1 + t1 > K)break;
		cur1 += t1; ans2++;
		vs[t2] = 1;
		for(auto [i, j] : adj[t2]){
			if(!vs[i])pq.push({t1 + j, i});
		}
	}
	for(int i = 0; i < N; i++){
		adj[i].clear();
	}
	return max(ans, ans2);
}

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