Submission #829627

#	Time	Username	Problem	Language	Result	Execution time	Memory
829627		CSQ31	Two Currencies (JOI23_currencies)	C++17	100 / 100	2037 ms	182720 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXNODE = 2e7+5;
int lf[MAXNODE],rg[MAXNODE],cnt[MAXNODE],ndcnt = 0;
ll sum[MAXNODE];
int new_node(){
	ndcnt++;
	return ndcnt;
}
int new_node(int v){
	ndcnt++;
	sum[ndcnt] = sum[v];
	cnt[ndcnt] = cnt[v];
	lf[ndcnt] = lf[v];
	rg[ndcnt] = rg[v];	
	return ndcnt;
}
//get the double euler tour array
//set cost(i) at tin(i) and -cost(i) at tout(i)
int upd(int v,int pos,int l,int r,ll val){
	int u = new_node(v);
	if(l==r){
		sum[u]+=val;
		if(val>0)cnt[u]++;
		if(val<0)cnt[u]--;
		return u;
	}
	int tm = (l+r)/2;
	if(pos<=tm){
		if(!lf[v])lf[v] = new_node();
		lf[u] = upd(lf[v],pos,l,tm,val);
	}else{
		if(!rg[v])rg[v] = new_node();
		rg[u] = upd(rg[v],pos,tm+1,r,val);
	}
	
	sum[u] = cnt[u] = 0;
	if(lf[u]){
		sum[u]+=sum[lf[u]];
		cnt[u]+=cnt[lf[u]];
	}
	if(rg[u]){
		sum[u]+=sum[rg[u]];
		cnt[u]+=cnt[rg[u]];
	}
	return u;
}
ll query(int v,int l,int r,int tl,int tr){
	if(l==tl && r==tr)return sum[v];
	int tm = (tl+tr)/2;
	
	if(!lf[v])lf[v] = new_node();
	if(!rg[v])rg[v] = new_node();
	
	if(r<=tm)return query(lf[v],l,r,tl,tm);
	else if(l>tm)return query(rg[v],l,r,tm+1,tr);
	else{
		return query(lf[v],l,tm,tl,tm)+query(rg[v],tm+1,r,tm+1,tr);
	}
	
}
ll query2(int v,int l,int r,int tl,int tr){
	if(l==tl && r==tr)return cnt[v];
	int tm = (tl+tr)/2;
	
	if(!lf[v])lf[v] = new_node();
	if(!rg[v])rg[v] = new_node();
	
	if(r<=tm)return query2(lf[v],l,r,tl,tm);
	else if(l>tm)return query2(rg[v],l,r,tm+1,tr);
	else{
		return query2(lf[v],l,tm,tl,tm)+query2(rg[v],tm+1,r,tm+1,tr);
	}
	
}
///////persistent seg
const int MAXN = 5e5+5;
vector<int>adj[MAXN];
int tin[MAXN],tout[MAXN],dep[MAXN],par[19][MAXN],timer = 0;
int cost[MAXN],ett[2*MAXN];
void dfs(int v,int u){
	tin[v] = ++timer;
	ett[tin[v]] = v;
	for(int x:adj[v]){
	    if(x == u)continue;	
	    par[0][x] = v;
	    dep[x] = dep[v]+1;
	    for(int i=1;i<=18;i++){
			par[i][x] = par[i-1][par[i-1][x]];
		}
		dfs(x,v);
	}
	tout[v] = ++timer;
	ett[tout[v]] = -v;
}
bool ancestor(int v,int u){return(tin[v] >= tin[u] && tout[u] >= tout[v]);}//is u an ancestor of v?
int lca(int v,int u){
	if(dep[v] > dep[u])swap(u,v);
	int dist = dep[u]-dep[v];
	for(int i=0;dist;i++,dist>>=1){
		if(dist&1)u = par[i][u];
	}
	if(u == v)return u;
	for(int i=18;i>=0;i--){
		if(par[i][v] != par[i][u]){
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][v];
}

int main()
{
	owo
	int n,m,q;
	cin>>n>>m>>q;
	vector<pii>ed(n),C(m);
	for(int i=1;i<n;i++)cin>>ed[i].fi>>ed[i].se;
	for(int i=0;i<m;i++)cin>>C[i].se>>C[i].fi;
	
	vii p(n);
	sort(all(C));
	int N = n;
	for(int i=0;i<m;i++){
		N++; //label this guy as N
		p[C[i].se].pb(N);
		cost[N] = C[i].fi;
	}
	for(int i=1;i<n;i++){
		int a = ed[i].fi;
		int b = ed[i].se;
		for(int x:p[i]){
			adj[a].pb(x);
			adj[x].pb(a);
			a = x;
		}
		adj[a].pb(b);
		adj[b].pb(a);
	}
	dfs(1,-1);
	vector<int>root(2*N+1);
	for(int i=1;i<=2*N;i++){
		root[i] = new_node(root[i-1]);
		
		int v = abs(ett[i]);
		if(v > n){
			if(ett[i]>0)root[i] = upd(root[i],v,1,N,cost[v]);
			else        root[i] = upd(root[i],v,1,N,-cost[v]);
		}
	}
	while(q--){
		int s,t,x;
		ll y;
		cin>>s>>t>>x>>y;
		int v = lca(s,t);
		int l = 1,r = N;
		//cout<<s<<" "<<t<<" "<<v<<'\n';
		while(r>=l){
			int tm = (l+r)/2;
			ll a = query(root[tin[v]],1,tm,1,N);
			ll b = query(root[tin[s]],1,tm,1,N);
			ll c = query(root[tin[t]],1,tm,1,N);
			if(b+c-2*a > y)r = tm-1;
			else l = tm+1;
		}
		int gol = cnt[root[tin[s]]] + cnt[root[tin[t]]] - 2*cnt[root[tin[v]]];
		gol -= query2(root[tin[s]],1,r,1,N) + query2(root[tin[t]],1,r,1,N);
		gol += 2*query2(root[tin[v]],1,r,1,N);
		if(x>=gol)cout<<x-gol<<'\n';
		else cout<<-1<<'\n';
	}
	
	
	
	
}

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