Submission #1298748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298748		Jawad_Akbar_JJ	Two Currencies (JOI23_currencies)	C++20	0 / 100	5096 ms	65348 KiB

currencies

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define int long long
const int N = 1<<18, K = 320, B = 320;
vector<pair<int,int>> nei[N];
vector<int> vec[N], adj[N];
vector<pair<int, pair<int, int>>> ord;
int Par[N], blk[N], st[N], en[N], s[N], t[N], x[N], y[N], cr0, cr1, cr2;
int cnt1[N], cnt2[N], Sum[N], num[N], arr[N], seen[N], Ans[N], inf = 2e18;

void block(vector<int> me){
	++cr1;
	for (int j : me)
		blk[j] = cr1;
}

void dfs0(int u, int p){
	// cout<<u<<" "<<p<<endl;
	for (auto [i, id] : nei[u]){
		if (i == p)
			continue;
		int lst = u;
		for (int j : vec[id]){
			adj[lst].push_back(++cr2);
			num[cr2] = j;
			lst = cr2;
		}
		adj[lst].push_back(i);
		dfs0(i, u);
	}
}

vector<int> dfs(int u){
	st[u] = ++cr0;
	vector<int> me;
	for (int i : adj[u]){
		Par[i] = u;
		vector<int> nw = dfs(i);
		me.insert(me.end(), nw.begin(), nw.end());
		if (me.size() >= K)
			block(me), me = {};
	}
	en[u] = ++cr0;
	me.push_back(u);
	return me;
}

void toggle(int id){
	if (num[id] == 0)
		return;
	int cur = upper_bound(arr, arr + N, num[id] - 1) - arr, tp = (seen[id] == 0 ? 1 : -1);

	cnt1[cur] += tp;
	cnt2[cur / B] += tp;
	Sum[cur / B] += tp * num[id];
	seen[id] ^= 1;
}

void moveLR(int u, int v){
	while (st[u] > st[v] or en[u] < en[v]){
		toggle(u);
		u = Par[u];
	}
	while (v != u){
		toggle(v);
		v = Par[v];
	}
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, m, q;
	cin>>n>>m>>q;

	for (int i=1, a, b;i<n;i++){
		cin>>a>>b;
		nei[a].push_back({b, i});
		nei[b].push_back({a, i});
	}

	for (int i=1, p, c;i<=m;i++){
		cin>>p>>c;
		vec[p].push_back(c);
		arr[i-1] = c;
	}

	sort(arr, arr + m);
	m = unique(arr, arr + m) - arr;
	for (int i=m;i<N;i++)
		arr[i] = inf;

	cr2 = n + 1;
	dfs0(1, 0);
	block(dfs(1));

	for (int i=1;i<=q;i++){
		cin>>s[i]>>t[i]>>x[i]>>y[i];
		ord.push_back({blk[s[i]], {t[i], i}});
	}

	sort(ord.begin(), ord.end());

	int L = 1, R = 1;
	for (auto [vl, pr] : ord){
		int id = pr.second, cur = -1;
		moveLR(L, s[id]);
		moveLR(R, t[id]);
		L = s[id], R = t[id];
		
		while (arr[cur + B] != inf and y[id] >= Sum[cur / B + 1])
			cur += B, y[id] -= Sum[cur / B];
		while (arr[cur+1] != inf and cnt1[cur + 1] * arr[cur + 1] <= y[id])
			cur++, y[id] -= cnt1[cur] * arr[cur];

		int gld = cnt1[++cur] - y[id] / arr[cur];
		while (cur % B != B - 1)
			cur++, gld += cnt1[cur];
		while (cur + B < N)
			cur += B, gld += cnt2[cur / B];
		Ans[id] = max(-1LL, x[id] - gld);
	}

	for (int i=1;i<=q;i++)
		cout<<Ans[i]<<' ';
	cout<<'\n';

}

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