제출 #956235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
956235		Nonoze	Two Currencies (JOI23_currencies)	C++17	28 / 100	5076 ms	340792 KiB

currencies

/*
*	Author: Nonoze
*	Created: Sunday 31/03/2024
*/
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
#define int long long


#ifdef _IN_LOCAL
	#include <bits/DebugTemplate.h>
#else
	#define dbg(...) ;
#endif
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) cout << x << endl, return;
const int MOD = 1e9+7;
const ll inf = 1e18;


template<typename T> constexpr bool cmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> constexpr bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }


void solve();

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}



struct node
{
	int left, right;
	int sum, lazy;
	node() {
		sum=0, lazy=-1, left=-1, right=-1;
	}
};

node st[100005*64];
int cnt=1;

int query(int root, int left, int right, int qRight) {
	if (right<=qRight) return st[root].sum;
	int mid=(left+right)/2;
	int s1=0, s2=0;
	if (st[root].left!=-1) s1=query(st[root].left, left, mid, qRight);
	if (st[root].right!=-1 && mid<qRight) s2=query(st[root].right, mid+1, right, qRight);
	return s1+s2;
}

void update(int root, int left, int right, int qPoint, int nValue) {
	if (left==right) {
		st[root].sum+=nValue*left;
		return;
	}
	int mid=(left+right)/2;
	if (mid>=qPoint) {
		if (st[root].left==-1) st[root].left = cnt++;
		update(st[root].left, left, mid, qPoint, nValue);
		st[root].sum=st[st[root].left].sum;
		if (st[root].right!=-1) st[root].sum+=st[st[root].right].sum;
	}
	else {
		if (st[root].right==-1) st[root].right = cnt++;
		update(st[root].right, mid+1, right, qPoint, nValue);
		st[root].sum=st[st[root].right].sum;
		if (st[root].left!=-1) st[root].sum+=st[st[root].left].sum;
	}
}



int n, m, q;
vector<set<pair<int, int>>> adj;
vector<int> depth, nb;
vector<vector<int>> up;
int base=0;

void dfs(int s, int prec=-1) {
	for (auto u: adj[s]) {
		if (u.fi==prec) continue;
		nb[u.fi]=nb[s]+(u.se?1:0);
		if (u.se) base=u.se;
		depth[u.fi]=depth[s]+1;
		up[u.fi][0]=s;
		for (int i=1; i<20; i++) {
			up[u.fi][i]=up[ up[u.fi][i-1] ][i-1];
		}
		dfs(u.fi, s);
	}
}

int get_lca(int a, int b) {
	if (depth[a]<depth[b]) swap(a, b);
	int k=depth[a]-depth[b];
	for (int i=0; i<20; i++) {
		if (k&(1<<i)) {
			a=up[a][i];
		}
	}
	if (a==b) return a;
	for (int i=19; i>=0; i--) {
		if (up[a][i]!=up[b][i]) {
			a=up[a][i];
			b=up[b][i];
		}
	}
	return up[a][0];
}

void subtask2() {
	depth.resize(n), nb.resize(n), up.resize(n, vector<int>(20));
	dfs(0);
	while (q--) {
		int s, t, a, b; cin >> s >> t >> a >> b;
		int lca=get_lca(--s, --t);
		int sumnb=nb[s]+nb[t]-2*nb[lca];
		int take=b/base;
		int res=-1;
		take=sumnb-take;
		if (take<=0) {
			cout << a << endl;
			continue;
		}
		cmax(res, a-take);
		cout << res << endl;
	}
}


int ask(ordered_multiset<int> &ost, int s, int t, int a, int b) {
	if (ost.empty()) return a;
	int l=0, r=*ost.rbegin(), ans=0;
	while (l<=r) {
		int mid=(l+r)/2;
		if (query(0, 1, (int)1e9, mid)<=b) {
			l=mid+1;
			ans=mid;
		} else r=mid-1;
	}
	auto ub=ost.lower_bound(ans);
	if (ub==ost.end()) return a;
	int comp=ost.order_of_key(*ub);
	b-=query(0, 1, (int)1e9, ans);
	comp+=b/(*ub);
	comp=sz(ost)-comp;
	if (comp<=0) comp=0;
	if (comp>a) comp=a+1;
	return a-comp;
}


void subtask3() {
	vector<int> ordre(1, 0);
	vector<pair<int, int>> nxt(n, {-1, -1});
	vector<int> empl(n, 0);
	int lst=-1;
	for (int i=0; i<n; i++) {
		for (auto u: adj[ordre.back()]) {
			if (u.fi!=lst) {
				nxt[ordre.back()]={u.fi, u.se};
				lst=ordre.back();
				ordre.push_back(u.fi);
				empl[ordre.back()]=sz(ordre)-1;
				break;
			}
		}
	}


	vector<int> answers(q);
	vector<pair<vector<int>, int>> queries;
	for (int i=0; i<q; i++) {
		int s, t, a, b; cin >> s >> t >> a >> b;
		if (--s>--t) swap(s, t);
		queries.push_back({{s, t, a, b}, i});
	}
	sort(all(queries), [&](auto &a, auto &b){
		if ((a.fi[0]/300)!=(b.fi[0]/300)) return (a.fi[0]/300)<(b.fi[0]/300);
		return a.fi[1]<b.fi[1];
	});
	int left=empl[queries[0].fi[0]], right=left;
	ordered_multiset<int> ost;
	for (int i=0; i<q; i++) {
		int s=queries[i].fi[0], t=queries[i].fi[1];
		while (right<empl[t]) {
			if (nxt[ordre[right]].se) {
				update(0, 1, (int)1e9, nxt[ordre[right]].se, 1);
				ost.insert(nxt[ordre[right]].se);
			}
			right++;
		}
		while (left>empl[s]) {
			left--;
			if (nxt[ordre[left]].se) {
				update(0, 1, (int)1e9, nxt[ordre[left]].se, 1);
				ost.insert(nxt[ordre[left]].se);
			}
		}
		while (left<empl[s]) {
			if (nxt[ordre[left]].se) {
				update(0, 1, (int)1e9, nxt[ordre[left]].se, -1);
				ost.erase(--ost.lower_bound(nxt[ordre[left]].se));
			}
			left++;
		}
		while (right>empl[t]) {
			right--;
			if (nxt[ordre[right]].se) {
				update(0, 1, (int)1e9, nxt[ordre[right]].se, -1);
				ost.erase(--ost.lower_bound(nxt[ordre[right]].se));
			}
		}
		answers[queries[i].se]=ask(ost, s, t, queries[i].fi[2], queries[i].fi[3]);
	}
	for (auto u: answers) cout << u << endl;
}


void solve() {
	cin >> n >> m >> q;
	adj.resize(n);
	bool sub3=true;
	vector<pair<int, int>> edges;
	for (int i=1; i<n; i++) {
		int u, v; cin >> u >> v;
		edges.push_back({--u, --v});
		if (v!=u+1) sub3=false;
		adj[u].insert({v, 0});
		adj[v].insert({u, 0});
	}
	vector<stack<int>> updates(n-1);
	for (int i=0; i<m; i++) {
		int p, c; cin >> p >> c;
		updates[--p].push(c);
	}
	for (int i=0; i<sz(updates); i++) {
		if (updates[i].empty()) continue;
		auto act=updates[i];
		int u=edges[i].fi, v=edges[i].se;
		adj[u].erase({v, 0}); adj[v].erase({u, 0});
		adj[u].insert({v, act.top()});
		adj[v].insert({u, act.top()});
		int weightbase=act.top(); act.pop();
		while (!act.empty()) {
			int weight=act.top(); act.pop();
			adj[u].erase({v, weightbase}); adj[v].erase({u, weightbase});
			adj[u].insert({n, weight});
			adj.push_back({});
			adj[n].insert({u, weight});
			adj[v].insert({n, weightbase});
			adj[n].insert({v, weightbase});
			u=n;
			n++;
		}
	}
	if (sub3) return subtask3();
	return subtask2();
}

• Subtask 1: 0 / 10
• Subtask 2: 28 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32