Submission #1026635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026635		Unforgettablepl	Two Currencies (JOI23_currencies)	C++17	100 / 100	3084 ms	39844 KiB

currencies

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

#define int long long

const int INF = 1e15;
const int SQRT = 450;

struct fenwick{
	vector<int> tree;
	int n;
	fenwick(int n):tree(n+1),n(n){}
	int get(int k){
		int ans = 0;
		while(k){
			ans+=tree[k];
			k-=k&-k;
		}
		return ans;
	}
	void add(int k,int x){
		k++;
		while(k<=n){
			tree[k]+=x;
			k+=k&-k;
		}
	}
	int search(int x){
		int ans = 0;
		for(int bit=16;bit>=0;bit--){
			if((ans|(1<<bit))<=n and tree[ans|(1<<bit)]<=x){
				ans|=(1<<bit);
				x-=tree[ans];
			}
		}
		return ans;
	}
};

struct query{
	int l,r,silver,gold,idx;
	query(int l,int r,int silver,int gold,int idx):l(l),r(r),silver(silver),gold(gold),idx(idx){}
	bool operator<(const query& other) const {
		return l/SQRT == other.l/SQRT ? r<other.r : l<other.l;
	}
};

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,q;
	cin >> n >> m >> q;
	vector<vector<pair<int,int>>> adj(n+1);
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		adj[u].emplace_back(v,i);
		adj[v].emplace_back(u,i);
	}
	vector<vector<int>> checkpointbyidx(n+1);
	vector<pair<int,int>> checkpoints(m);
	for(auto&[cost,loc]:checkpoints)cin>>loc>>cost;
	sort(checkpoints.begin(),checkpoints.end());
	for(int i=0;i<m;i++)checkpointbyidx[checkpoints[i].second].emplace_back(i);
	vector<pair<int,int>> tour(1);
	vector<int> in(n+1);
	vector<int> out(n+1);
	int idx = 0;
	function<void(int,int)> dfs = [&](int x,int p){
		int paridx = 0;
		for(auto&[v,i]:adj[x])if(v==p)paridx=i;
		for(auto&i:checkpointbyidx[paridx]){
			tour.emplace_back(i,checkpoints[i].first);
			idx++;
		}
		in[x]=idx;
		for(auto&[v,i]:adj[x])if(v!=p)dfs(v,x);
		out[x]=idx+1;
		for(auto&i:checkpointbyidx[paridx]){
			tour.emplace_back(i,checkpoints[i].first);
			idx++;
		}
	};
	dfs(1,0);
	vector<int> ans(q);
	vector<query> queries;
	for(int i=0;i<q;i++){
		int s,t,x,y;cin>>s>>t>>x>>y;
		if(out[t]<in[s])queries.emplace_back(out[t],in[s],y,x,i);
		else if(out[s]<in[t])queries.emplace_back(out[s],in[t],y,x,i);
		else if(out[s]<out[t]) queries.emplace_back(out[s],out[t]-1,y,x,i);
		else queries.emplace_back(out[t],out[s]-1,y,x,i);
	}
	sort(queries.begin(),queries.end());
	int l = 1;
	int r = 0;
	fenwick costchosen(m);
	fenwick amtchosen(m);
	vector<int> addcnt(m+1);
	int totchosen = 0;
	auto flip = [&](pair<int,int> x){
		if(addcnt[x.first]&1){
			costchosen.add(x.first,-x.second);
			amtchosen.add(x.first,-1);
			totchosen--;
		} else {
			costchosen.add(x.first,x.second);
			amtchosen.add(x.first,1);
			totchosen++;
		}
		addcnt[x.first]++;
	};
	for(auto&qu:queries){
		while(l<qu.l){
			flip(tour[l++]);
		}
		while(qu.l<l){
			flip(tour[--l]);
		}
		while(qu.r<r){
			flip(tour[r--]);
		}
		while(r<qu.r){
			flip(tour[++r]);
		}
		ans[qu.idx] = max(-1ll,qu.gold-totchosen+amtchosen.get(costchosen.search(qu.silver))); 
	}
	for(int&i:ans)cout<<i<<'\n';
}

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