Submission #743459

#	Time	Username	Problem	Language	Result	Execution time	Memory
743459		emptypringlescan	Two Currencies (JOI23_currencies)	C++17	10 / 100	5058 ms	197552 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
	int s,e,m;
	long long val;
	long long cnt;
	node *l,*r;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2LL;
		l=r=NULL;
		val=cnt=0LL;
	}
	void prop(){
		if(l==NULL){
			l=new node(s,m);
			r=new node(m+1LL,e);
		}
	}
	void update(int S, int N){
		if(s==e){
			if(N==1LL){
				val+=(long long)s;
				cnt++;
			}
			else{
				val-=(long long)s;
				cnt--;
			}
			return;
		}
		prop();
		if(S<=m) l->update(S,N);
		else r->update(S,N);
		val=l->val+r->val;
		cnt=l->cnt+r->cnt;
	}
	long long query(long long V){
		if(s==e){
			assert(s!=0LL);
			assert(cnt*s==val);
			return min(V/(long long)s,cnt);
		}
		prop();
		if(l->val>V) return l->query(V);
		else return l->cnt+r->query(V-l->val);
	}
} *root;
vector<int> adj[300005],eul;
int fi[300005],se[300005];
long long cost[300005];
void dfs(int x, int p){
	fi[x]=eul.size();
	eul.push_back(x);
	for(int i:adj[x]){
		if(i!=p) dfs(i,x);
	}
	se[x]=eul.size();
	eul.push_back(x);
}
const int MAXN = 300050;
const int LOGN = 20;
int p[LOGN+1][MAXN], h[MAXN];   //h: number of edges from root
bitset<MAXN> visited;
void dfss(int x) {
    if (visited[x]) return;
    visited[x] = 1LL;
    for (int k = 0LL; k < LOGN; ++k) {
        if (p[k][x] == -1LL) break;
        p[k+1LL][x] = p[k][p[k][x]];
    }
    for (int it:adj[x]) {
        if (visited[it]) continue;
        p[0][it] = x;
        h[it] = h[x] + 1LL;
        dfss(it);
    }
}

/* Query */
int lca(int a, int b) { //h[a] < h[b]
    if (h[a] > h[b]) swap(a, b);
    /* advance b by h[b] - h[a] parents */
    for (int k = 0, d = h[b] - h[a]; k < LOGN; ++k) {
        if (d & (1<<k))  b = p[k][b];
    }
    if (a == b) return a;
    assert(h[a] == h[b]); //same height
    /* to be continued */
    for (int k = LOGN-1; k >= 0; --k) {
        if (p[k][a] != p[k][b]) 
            a = p[k][a], b = p[k][b];
    }
    assert(p[0][a] == p[0][b]);        //same immediate parent
    return p[0][a];
}
bool cmp(pair<pair<int,int>,pair<pair<int,pair<int,long long> >,int> > a,pair<pair<int,int>,pair<pair<int,pair<int,long long> >,int> > b){
	if(a.first.first==b.first.first){
		if((a.first.first&1LL)==0LL) return a.first.second<b.first.second;
		else return a.first.second>b.first.second;
	}
	return a.first.first<b.first.first;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(p,-1,sizeof(p));
	int n,m,q;
	cin >> n >> m >> q;
	vector<pair<int,int> > edges;
	for(int i=0; i<n-1; i++){
		int a,b;
		cin >> a >> b;
		edges.push_back({a,b});
	}
	int cnt=n+1LL;
	for(int i=0; i<m; i++){
		int a;
		long long b;
		cin >> a >> b;
		cost[cnt]=b;
		edges.push_back({cnt,edges[a-1LL].second});
		edges[a-1LL].second=cnt;
		cnt++;
	}
	for(auto i:edges){
		adj[i.first].push_back(i.second);
		adj[i.second].push_back(i.first);
	}
	dfs(1LL,-1LL);
	dfss(1LL);
	int buc=450LL;
	long long ans[q];
	pair<pair<int,int>,pair<pair<int,pair<int,long long> >,int> > qu[q];
	pair<int,int> org[q];
	for(int i=0LL; i<q; i++){
		int a,b;
		long long c,d;
		cin >> a >> b >> c >> d;
		org[i]={a,b};
		int x=0LL,y=0LL,o=-1LL;
		if(se[a]<fi[b]){
			x=se[a]; y=fi[b];
			o=lca(a,b);
		}
		else if(se[b]<fi[a]){
			x=se[b]; y=fi[a];
			o=lca(a,b);
		}
		else if(fi[a]<fi[b]){
			x=fi[a]; y=fi[b];
		}
		else{
			x=fi[b]; y=fi[a];
		}
		ans[i]=c;
		qu[i]={{x/buc,y},{{o,{i,d}},x}};
	}
	sort(qu,qu+q,cmp);
	int c1=0LL,c2=0LL,nds=0LL;
	root=new node(0LL,2000000005LL);
	int got[300005];
	memset(got,0,sizeof(got));
	for(int i=0LL; i<q; i++){
		while(c2<=qu[i].first.second){
			if(got[eul[c2]]==0LL){
				got[eul[c2]]=1LL;
				nds++;
				root->update(cost[eul[c2]],1LL);
			}
			else{
				got[eul[c2]]=0LL;
				nds--;
				root->update(cost[eul[c2]],-1LL);
			}
			c2++;
		}
		while(c1>qu[i].second.second){
			c1--;
			if(got[eul[c1]]==0LL){
				got[eul[c1]]=1LL;
				nds++;
				root->update(cost[eul[c1]],1LL);
			}
			else{
				got[eul[c1]]=0LL;
				nds--;
				root->update(cost[eul[c1]],-1LL);
			}
		}
		while(c2>qu[i].first.second+1LL){
			c2--;
			if(got[eul[c2]]==0LL){
				got[eul[c2]]=1LL;
				nds++;
				root->update(cost[eul[c2]],1LL);
			}
			else{
				got[eul[c2]]=0LL;
				nds--;
				root->update(cost[eul[c2]],-1LL);
			}
		}
		while(c1<qu[i].second.second){
			if(got[eul[c1]]==0LL){
				got[eul[c1]]=1LL;
				nds++;
				root->update(cost[eul[c1]],1LL);
			}
			else{
				got[eul[c1]]=0LL;
				nds--;
				root->update(cost[eul[c1]],-1LL);
			}
			c1++;
		}
		if(qu[i].second.first.first!=-1LL){
			int o=qu[i].second.first.first;
			if(got[o]==0LL){
				got[o]=1LL;
				nds++;
				root->update(cost[o],1LL);
			}
			else{
				assert(false);
			}
		}
		int heh=root->query(qu[i].second.first.second.second);
		assert((eul[c1]==org[qu[i].second.first.second.first].first&&eul[c2-1]==org[qu[i].second.first.second.first].second)||(eul[c2-1]==org[qu[i].second.first.second.first].first&&eul[c1]==org[qu[i].second.first.second.first].second));
		ans[qu[i].second.first.second.first]-=(h[eul[c1]]+h[eul[c2-1]]-2LL*h[lca(eul[c1],eul[c2-1])]+1LL-heh);
		if(qu[i].second.first.first!=-1){
			int o=qu[i].second.first.first;
			if(got[o]==0LL){
				got[o]=1LL;
				nds++;
				root->update(cost[o],1LL);
			}
			else{
				got[o]=0LL;
				nds--;
				root->update(cost[o],-1LL);
			}
		}
	}
	for(int i=0; i<q; i++){
		if(ans[i]<0LL) cout << -1 << '\n';
		else cout << ans[i] << '\n';
	}
}
/*5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1*/

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