Submission #1136375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136375		dombly	Two Currencies (JOI23_currencies)	C++20	100 / 100	3701 ms	518192 KiB

currencies

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt")
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 262144; const ll E = 18; const ll INF = 2e18;

struct Node {
	map<ll,ll> m0; //{cost -> #}
	//map<ll,pii> mps; //{aggregate cost, aggregate # at val}
	vector<array<ll,3>> mps;
	ll cptot = 0;
	void prc() {
		//mps[-INF]={0,0};
		mps.push_back({-INF,0,0});
		ll nc = 0; ll vc = 0;
		for (pii p0: m0) {
			ll n1 = p0.second; ll c1 = p0.first;
			nc += n1; vc += n1*c1;
			//mps[c1]={vc,nc};
			mps.push_back({c1,vc,nc});
		}
	}
	Node(){}
	Node(vector<ll> v1) {
		for (ll x: v1) {
			if (x>0) {
				m0[x]++;
				cptot++;
			} else {
				m0[-x]--;
				cptot--;
			}
		}
		prc();
	}
	Node(Node n1, Node n2) {
		for (pii p0: n1.m0) {
			m0[p0.first]+=p0.second;
		}
		for (pii p0: n2.m0) {
			m0[p0.first]+=p0.second;
		}
		cptot = n1.cptot+n2.cptot;
		prc();
	}
	pii qry(ll x) {
		auto A0 = *(--upper_bound(mps.begin(),mps.end(),(array<ll,3>){x,INF,INF}));
		return (pii){A0[1],A0[2]};
		//return {(*A0).second;
	}
};

inline ll v2(ll x) {
	return __builtin_ctz(x);
}

inline ll l2(ll x) {
	return (31-__builtin_clz(x));
}

inline pii fz(pii p1, pii p2) {
	return ((p1.second<p2.second) ? p1 : p2);
}

vector<ll> floc(Nm,INF); //first location
vector<ll> lloc(Nm,-INF); //last location
vector<pii> adj[Nm];
ll radj[Nm];
ll ht[Nm];
ll locr[Nm]; //road location: index of bottom node 
Node st[2*Nm]; //euler tour segtree
vector<ll> ppe[Nm]; //preprocess edges
pii ett[Nm][E+1];

pii ginf(vector<ll>& v1, ll x) {
	ll a1=0,b1=0;
	for (auto A0: v1) {
		pii c1 = st[A0].qry(x);
		a1 += c1.first; b1 += c1.second;
	}
	return {a1,b1}; //{cost <=val, # <=val}
}

ll nv(vector<ll> v1, ll ctot) {
	ll cmin = 0; ll cmax = 2e9;
	//binary search for largest c for which
	//ginf(c).first<=ctot
	while (cmin != cmax) {
		ll ctest = (cmin+cmax+1)/2;
		if (ginf(v1,ctest).first<=ctot) {
			cmin = ctest;
		} else {
			cmax = ctest-1;
		}
	}
	pii gf0 = ginf(v1,cmin);
	pii gf1 = ginf(v1,cmin+1);
	if (gf0.second==gf1.second || gf0.first==ctot) {
		return gf0.second;
	} else {
		return (gf0.second+(ctot-gf0.first)/(cmin+1));
	}
}

ll lca(ll x, ll y) {
	x = floc[x]; y = floc[y];
	if (x>y) {
		swap(x,y);
	}
	ll lx = l2(y-x+1);
	return fz(ett[x][lx],ett[y-(1<<lx)+1][lx]).first;
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N,M,Q; cin >> N >> M >> Q;
	for (ll i=0;i<(N-1);i++) {
		ll a,b; cin >> a >> b; a--; b--;
		adj[a].push_back({b,i});
		adj[b].push_back({a,i});
	}
	vector<ll> ettv;
	stack<pii> st0; //euler tour
	st0.push({0,0});
	radj[0]=-1;
	ht[0]=0;
	while (!st0.empty()) {
		pii p0 = st0.top(); st0.pop();
		ll x = p0.first; ll t = p0.second;
		ettv.push_back(x);
		if (t==0) {
			for (pii p1: adj[x]) {
				ll y = p1.first; ll i = p1.second;
				if (y==radj[x]) {
					continue;
				}
				radj[y]=x;
				ht[y]=1+ht[x];
				locr[i]=y;
				st0.push({x,1});
				st0.push({y,0});
			}
		}
	}
	assert(ettv.size()<=Nm);
	for (ll i=0;i<ettv.size();i++) {
		//cout << "ettv: "<<ettv[i]<<"\n";
		floc[ettv[i]]=min(floc[ettv[i]],i);
		lloc[ettv[i]]=max(lloc[ettv[i]],i);
		ett[i][0]={ettv[i],ht[ettv[i]]};
	}
	for (ll e=1;e<=E;e++) {
		for (ll i=0;i<=(Nm-(1<<e));i++) {
			ett[i][e]=fz(ett[i][e-1],ett[i+(1<<(e-1))][e-1]);
		}
	}
	for (ll m=0;m<M;m++) {
		ll p,c; cin >> p >> c;
		p--;
		ppe[floc[locr[p]]-1].push_back(c);
		ppe[lloc[locr[p]]].push_back(-c);
	}
	for (ll i=0;i<Nm;i++) {
		st[i+Nm]=Node(ppe[i]);
	}
	// for (ll i=0;i<ettv.size();i++) {
	// 	cout << "i="<<i<<"\n";
	// 	cout << "ettv: "<<ettv[i]<<"\n";
	// 	cout << "ppe elem:\n";
	// 	for (ll x: ppe[i]) {
	// 		cout << x<<"\n";
	// 	}
	// }
	for (ll i=(Nm-1);i>=1;i--) {
		st[i]=Node(st[2*i],st[2*i+1]);
	}
	for (ll q=0;q<Q;q++) {
		ll s,t,x,y; cin >> s >> t >> x >> y;
		s--; t--;
		ll lc = lca(s,t);
		ll ntot = 0;
		vector<ll> vqry;
		ll a = floc[lc]; ll b = floc[s]-1;
		//cout << "s,t,lc="<<s<<","<<t<<","<<lc<<"\n";
		//cout << "a,b="<<a<<","<<b<<"\n";
		while (a<=b) {
			ll va = v2(a); ll vb = v2(b+1);
			if (va<vb) {
				ll p = (a>>va)+(1<<(E-va));
				//cout << "p="<<p<<", cp="<<st[p].cptot<<"\n";
				ntot += st[p].cptot;
				vqry.push_back(p);
				a += (1<<va);
			} else {
				ll p = (b>>vb)+(1<<(E-vb));
				//cout << "p="<<p<<", cp="<<st[p].cptot<<"\n";
				ntot += st[p].cptot;
				vqry.push_back(p);
				b -= (1<<vb);
			}
		}
		a = floc[lc]; b = floc[t]-1;
		//cout << "a,b="<<a<<","<<b<<"\n";
		while (a<=b) {
			ll va = v2(a); ll vb = v2(b+1);
			if (va<vb) {
				ll p = (a>>va)+(1<<(E-va));
				//cout << "p="<<p<<", cp="<<st[p].cptot<<"\n";
				ntot += st[p].cptot;
				vqry.push_back(p);
				a += (1<<va);
			} else {
				ll p = (b>>vb)+(1<<(E-vb));
				//cout << "p="<<p<<", cp="<<st[p].cptot<<"\n";
				ntot += st[p].cptot;
				vqry.push_back(p);
				b -= (1<<vb);
			}
		}
		ll utot = nv(vqry,y);
		//cout << "utot="<<utot<<"\n";
		if ((x+utot)<ntot) {
			cout << "-1\n";
		} else {
			cout << (x+utot-ntot)<<"\n";
		}

	} 
}
//0 2 0 1 4 1 3 1 0

//  0
//1   2
//ett: 01020
//edges: (01) (10) (02) (20)

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