Submission #1243770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243770		justinlgl20	Two Currencies (JOI23_currencies)	C++20	100 / 100	1073 ms	60744 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define all(x) (x).begin(), (x).end()
 
template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {
    int f = 0; os << '{'; for (auto &i: x) os << (f++ ? ", " : ""), os << i; os << "}";
    return os;
}
 
void _print() {cerr << "]\n";}
 
template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}
 
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

#define pii pair<int, int>
#define f first
#define s second

namespace ds{
	const int n=100005;
	const int SQ=300;
	int cnt[(n/SQ)+5],sm[(n/SQ)+5],cn[n],smm[n];
	vector<int>c;unordered_map<int,int>comp;
	void init(){
		sort(all(c));
		c.resize(unique(all(c))-c.begin());
		for(int i=0;i<c.size();i++){
			comp[c[i]]=i;
		}
	}
	int query(int v){
		//given that we can use up to v silvers, returns how many things are leftover
		dbg(v);
		int cur=0,pos=0,c=0;
		for(int i=0;i<n/SQ and pos<ds::c.size();i++){
			if(cur+sm[i]<=v){
				cur+=sm[i];
				c+=cnt[i];
				pos+=SQ;
			}else{
				break;
			}
		}
		for(int i=0;i<SQ and pos<ds::c.size();i++){
			if(cur+smm[pos]<=v){
				cur+=smm[pos];
				c+=(cn[pos]);
				pos++;
			}else{
				break;
			}
		}
		dbg("HI",v,cur,ds::c[pos],pos);
		while(pos<ds::c.size() and cur+ds::c[pos]<=v){
			cur+=ds::c[pos];
			c++;
		}
		return c;
	}
	void add(int v){
		int real=c[v];
		//dbg("ADD",real);
		int bucket=v/SQ;
		smm[v]+=real;
		cn[v]++;
		sm[bucket]+=real;
		cnt[bucket]++;
	}
	void remove(int v){
		int real=c[v];
		//dbg("REM",real);
		int bucket=v/SQ;
		smm[v]-=real;
		cn[v]--;
		sm[bucket]-=real;
		cnt[bucket]--;
	}
}

vector<int>adj[100005];
pii e[100005];
vector<int> things[100005];
int depth[100005],tin[100005],tbitin[100005],tmid[100005],tout[100005],w[100005];
vector<int>v;

void d(int u,int p=-1){for(int i:adj[u]){if(i==p)continue;depth[i]=depth[u]+1;d(i,u);}}
int jmp[100006][20],ts[100005],pmo[100005];
int counter=0;

void dfs(int u,int p=-1){
	ts[u]=counter++;
	jmp[u][0]=p;
	for(int i=1;i<20;i++){
		if(jmp[u][i-1]!=-1){
			jmp[u][i]=jmp[jmp[u][i-1]][i-1];
		}
	}
	tin[u]=v.size();
	dbg(u,things[u],adj[u]);
	for(auto i:things[u]){ v.push_back(i); }
	tbitin[u]=v.size();
	for(int i:adj[u]){
		if(i==p)continue;
		depth[i]=depth[u]+1;
		dfs(i,u);
	}
	tmid[u]=v.size();
	for(auto i:things[u]){ v.push_back(i); }
	tout[u]=v.size();
	pmo[u]=counter++;
}

bool is_anc(int a,int b){
	return ts[a]<=ts[b] and pmo[b]<=pmo[a];
}

int lca(int a,int b){
	if(is_anc(a,b))return a;
	if(is_anc(b,a))return b;
	return 1;
}

int dist(int u,int v){
	return depth[u]+depth[v]-2*depth[lca(u,v)];
}

inline int64_t hilbertOrder(int x, int y, int pow, int rotate) {
	if (pow == 0) { return 0; }
	int hpow = 1 << (pow-1);
	int seg = (x < hpow) ? ( (y < hpow) ? 0 : 3) : ( (y < hpow) ? 1 : 2);
	seg = (seg + rotate) & 3;
	const int rotateDelta[4] = {3, 0, 0, 1};
	int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
	int nrot = (rotate + rotateDelta[seg]) & 3;
	int64_t subSquareSize = int64_t(1) << (2*pow - 2);
	int64_t ans = seg * subSquareSize;
	int64_t add = hilbertOrder(nx, ny, pow-1, nrot);
	ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
	return ans;
}

struct query{
	int l,r,s,t,x,y,ans,val,inx;
	bool operator<(query &other){
		return val<other.val;	
	}
};
query q[100005];

int32_t main(){
	int n,m,qq;cin>>n>>m>>qq;
	for(int i=0;i<n-1;i++){cin>>e[i].f>>e[i].s;adj[e[i].f].push_back(e[i].s);adj[e[i].s].push_back(e[i].f);}
	d(1);

	for(int i=0;i<n-1;i++){if(depth[e[i].f]>depth[e[i].s])swap(e[i].f,e[i].s);}
	for(int i=0;i<m;i++){int p,v;cin>>p>>v;p--;things[e[p].s].push_back(i);::w[i]=v;dbg(e[p].s,w[i]);ds::c.push_back(w[i]);}
	ds::init();
	for(int i=0;i<m;i++)w[i]=ds::comp[w[i]];
	for(int i=1;i<=n;i++){
		dbg(i,things[i]);
	}
	dfs(1);
	dbg(::v);
	dbg(qq);
	for(int i=0;i<qq;i++){
		dbg(i);
		cin>>q[i].s>>q[i].t>>q[i].x>>q[i].y;q[i].inx=i;
		//if(tin[q[i].s]>tin[q[i].t])swap(q[i].s,q[i].t);
		if(ts[q[i].s]>ts[q[i].t])swap(q[i].s,q[i].t);
		// s is higher
		//if(tin[q[i].s]<=tin[q[i].t] and tout[q[i].t]<=tout[q[i].s]){
		if(is_anc(q[i].s,q[i].t)){
			q[i].l=tbitin[q[i].s];q[i].r=tbitin[q[i].t]-1;
		}else{
			q[i].l=tmid[q[i].s];q[i].r=tbitin[q[i].t]-1;
		}
		dbg(q[i].s,q[i].t,q[i].l,q[i].r);
		q[i].val=hilbertOrder(q[i].l,q[i].r,20,0);
	}
	sort(q,q+qq);
	vector<int>cnt(m);
	int l=0,r=0;cnt[v[0]]++;ds::add(w[v[0]]);
	//set<int>s;s.insert(v[0]);
	int pathlen=1;
	function<void(int)>add=[&](int i){
		cnt[i]++;
		if(cnt[i]==1){ds::add(w[i]);pathlen++;}//s.insert(i);}
		if(cnt[i]==2){ds::remove(w[i]);pathlen--;}//s.erase(s.find(i));}
	};
	function<void(int)>rem=[&](int i){
		if(cnt[i]==2){ds::add(w[i]);pathlen++;}//s.insert(i);}
		if(cnt[i]==1){ds::remove(w[i]);pathlen--;}//s.erase(s.find(i));}
		cnt[i]--;
	};
	vector<int>ans(qq);
	for(int i=0;i<qq;i++){
		dbg(i,q[i].l,q[i].r,q[i].s,q[i].t);
		while(l>q[i].l){
			l--; add(v[l]);
		}
		while(r<q[i].r){
			r++; add(v[r]);
		}
		while(l<q[i].l){
			rem(v[l]);l++;
		}
		while(r>q[i].r){
			rem(v[r]);r--;
		}
		auto idk=ds::query(q[i].y);//this is min golds needed
		//int pathlen=dist(q[i].s,q[i].t);// dist between q[i].s and q[i].t in terms of edges
		//int pathlen=s.size();
		dbg(pathlen,idk);
		q[i].ans=q[i].x-(pathlen-idk);
		if(q[i].ans<0)q[i].ans=-1;
		ans[q[i].inx]=q[i].ans;
	}
	for(int i=0;i<qq;i++){
		cout<<ans[i]<<"\n";
	}

}

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