oj.uz

Submission #1036879

# Submission time Handle Problem Language Result Execution time Memory
1036879 2024-07-27T18:42:23 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 370 ms 275604 KB 
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define ll long long
const int mxn=5e5+5,M=1e9+7,sz=(1<<21);
int n,r,q;
int st[mxn],fn[mxn],cnt,par[mxn],zr[mxn],bad=0;
ll f[mxn],rf[mxn],ans=1;
vector<int>v[mxn];
ll ferma(ll x,ll num=M-2){
	ll res=1;
	while(num){
		if(num&1)res=(res*x)%M;
		x=(x*x)%M;
		num>>=1;
	}
	return res;
}
void dfs(int z){
	st[z]=++cnt;
	zr[z]=1;
	for(auto i:v[z]){
		if(par[z]!=i){
			par[i]=z;
			dfs(i);
			zr[z]+=zr[i];
		}
	}
	fn[z]=cnt;
}
ll comb(ll x,ll y){
	//cout<<x<<" "<<y<<'\n';
	ll res=f[y]*rf[x];
	res%=M;
	res*=rf[y-x];
	return res%M;
}
struct segment{
	int val[sz];
	int get(int id,int L,int R,int l,int r){
		if(L>=R || L>=r || l>=r || l>=R)
			return 0;
		if(L>=l && R<=r)
			return val[id];
		int mid=(L+R)>>1,res=0;
		res+=get(id<<1,L,mid,l,r);
		res+=get((id<<1)+1,mid,R,l,r);
		return res;
	}
	void add(int id,int L,int R,int l,int x){
		if(L+1==R){
			val[id]=x;
			return ;
		}
		int mid=(L+R)>>1;
		if(l<mid)
			add(id<<1,L,mid,l,x);
		else
			add((id<<1)+1,mid,R,l,x);
		val[id]=val[id*2]+val[id*2+1];
		return ;
	}
}seg[2];
struct kirkhar{
	set<int>s[sz];
	int get(int id,int L,int R,int l){
		if(L+1==R)
			return (s[id].size())?*s[id].rbegin():0;
		int mid=(L+R)>>1,res;
		if(l<mid)
			res=get(id<<1,L,mid,l);
		else
			res=get((id<<1)+1,mid,R,l);
		if(res==0)
			return (s[id].size())?*s[id].rbegin():0;
		return res ;
	}
	void add(int id,int L,int R,int l,int r,int x,bool kos){
		if(L>=R || L>=r || l>=r || l>=R)
			return ;
		if(L>=l && R<=r){
			if(kos)
				s[id].insert(x);
			else
				s[id].erase(x);
			return ;
		}
		int mid=(L+R)>>1,res=0;
		add(id<<1,L,mid,l,r,x,kos);
		add((id<<1)+1,mid,R,l,r,x,kos);
		return ;
	}
}gg;
int main(){
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//cout.tie(0);
	cin>>n>>r;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1);
	f[0]=1;
	rf[0]=1;
	for(int i=1;i<=n+r;i++){
		f[i]=(f[i-1]*i)%M;
		rf[i]=ferma(f[i]);
		//cout<<f[i]<<" "<<rf[i]<<'\n';
	}
	seg[0].add(1,1,n+1,1,r);
	seg[1].add(1,1,n+1,1,n);
	gg.add(1,1,n+1,1,n+1,1,1);
	ans*=comb(n-1,n-1+r);
	ans%=M;
	cout<<ans<<'\n';
	cin>>q;
	while(q--){
		ll ty,x,y;
		cin>>ty>>x;
		if(ty==1){
			int ycnt=zr[x];
			cin>>y;
			ll zir=seg[0].get(1,1,n+1,st[x],fn[x]+1);
			ll zircnt=seg[1].get(1,1,n+1,st[x],fn[x]+1);
			y-=zir;
			ycnt-=zircnt;
			int p=gg.get(1,1,n+1,st[x]);
			if(p==0){
				return 0;
			}
			ll pre=seg[0].get(1,1,n+1,st[p],fn[p]+1);
			ll precnt=seg[1].get(1,1,n+1,st[p],fn[p]+1);
			if(pre<0){
				bad--;
			}
			else{
				ans*=ferma(comb(precnt-1,precnt-1+pre));
				ans%=M;
			}
			pre-=y;
			precnt-=ycnt;
			//cout<<y-zir<<" "<<ycnt-zircnt<<'\n';
			seg[0].add(1,1,n+1,st[x],y-zir);
			seg[1].add(1,1,n+1,st[x],ycnt-zircnt);
			seg[0].add(1,1,n+1,st[p],pre-seg[0].get(1,1,n+1,st[p]+1,fn[p]+1));
			seg[1].add(1,1,n+1,st[p],precnt-seg[1].get(1,1,n+1,st[p]+1,fn[p]+1));
//cout<<pre<<" "<<precnt<<'\n';
			if(pre<0){
				bad++;
			}
			else{
				ans*=comb(precnt-1,precnt+pre-1);
				ans%=M;
			}
			if(zir<0){
				bad++;
			}
			else{
				ans*=comb(ycnt-1,ycnt+y-1);
				ans%=M;
			}
			gg.add(1,1,n+1,st[x],fn[x]+1,st[x],1);
		}
		else{
			gg.add(1,1,n+1,st[x],fn[x]+1,st[x],0);
			ll zir=seg[0].get(1,1,n+1,st[x],fn[x]+1);
			ll zircnt=seg[1].get(1,1,n+1,st[x],fn[x]+1);
			int p=gg.get(1,1,n+1,st[x]);
			if(p==0){
				return 0;
			}

			ll pre=seg[0].get(1,1,n+1,st[p],fn[p]+1);
			ll precnt=seg[1].get(1,1,n+1,st[p],fn[p]+1);
			if(pre<0){
				bad--;
			}
			else{
				ans*=ferma(comb(precnt-1,precnt-1+pre));
				ans%=M;
			}
			if(zir<0){
				bad--;
			}
			else{
				ans*=ferma(comb(zircnt-1,zircnt+zir-1));
				ans%=M;
			}
			pre+=zir;
			precnt+=zircnt;
			
			seg[0].add(1,1,n+1,st[x],0);
			seg[1].add(1,1,n+1,st[x],0);
			seg[0].add(1,1,n+1,st[p],pre-seg[0].get(1,1,n+1,st[p]+1,fn[p]+1));
			seg[1].add(1,1,n+1,st[p],precnt-seg[1].get(1,1,n+1,st[p]+1,fn[p]+1));			
			if(pre<0){
				bad++;
			}
			else{
				ans*=comb(precnt-1,precnt+pre-1);
				ans%=M;
			}
			
		}
		if(bad)
			cout<<0<<'\n';
		else
			cout<<ans<<'\n';
	}
	return 0;

}

Compilation message

Main.cpp: In member function 'void kirkhar::add(int, int, int, int, int, int, bool)':
Main.cpp:89:20: warning: unused variable 'res' [-Wunused-variable]
   89 |   int mid=(L+R)>>1,res=0;
      |                    ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 135252 KB Output is correct
2 Correct 187 ms 133220 KB Output is correct
3 Correct 210 ms 132180 KB Output is correct
4 Correct 208 ms 134740 KB Output is correct
5 Correct 229 ms 130640 KB Output is correct
6 Correct 86 ms 115540 KB Output is correct
7 Correct 84 ms 115540 KB Output is correct
8 Correct 68 ms 113132 KB Output is correct
9 Correct 203 ms 127824 KB Output is correct
10 Correct 208 ms 127948 KB Output is correct
11 Correct 210 ms 128200 KB Output is correct
12 Correct 174 ms 124088 KB Output is correct
13 Correct 197 ms 133972 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 110676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 315 ms 275604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 370 ms 267088 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 135252 KB Output is correct
2 Correct 187 ms 133220 KB Output is correct
3 Correct 210 ms 132180 KB Output is correct
4 Correct 208 ms 134740 KB Output is correct
5 Correct 229 ms 130640 KB Output is correct
6 Correct 86 ms 115540 KB Output is correct
7 Correct 84 ms 115540 KB Output is correct
8 Correct 68 ms 113132 KB Output is correct
9 Correct 203 ms 127824 KB Output is correct
10 Correct 208 ms 127948 KB Output is correct
11 Correct 210 ms 128200 KB Output is correct
12 Correct 174 ms 124088 KB Output is correct
13 Correct 197 ms 133972 KB Output is correct
14 Incorrect 45 ms 110676 KB Output isn't correct
15 Halted 0 ms 0 KB -