oj.uz

Submission #1036886

# Submission time Handle Problem Language Result Execution time Memory
1036886 2024-07-27T18:57:45 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 825 ms 279652 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,pos[mxn];
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;
	pos[cnt]=z;
	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]);
			p=pos[p];
			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]);
			p=pos[p];
			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:90:20: warning: unused variable 'res' [-Wunused-variable]
   90 |   int mid=(L+R)>>1,res=0;
      |                    ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 138320 KB Output is correct
2 Correct 223 ms 136348 KB Output is correct
3 Correct 186 ms 135420 KB Output is correct
4 Correct 219 ms 138036 KB Output is correct
5 Correct 202 ms 133972 KB Output is correct
6 Correct 81 ms 115796 KB Output is correct
7 Correct 78 ms 115528 KB Output is correct
8 Correct 66 ms 113232 KB Output is correct
9 Correct 204 ms 130900 KB Output is correct
10 Correct 203 ms 131156 KB Output is correct
11 Correct 212 ms 131412 KB Output is correct
12 Correct 172 ms 127060 KB Output is correct
13 Correct 196 ms 136788 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 110584 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 309 ms 279652 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 138320 KB Output is correct
2 Correct 223 ms 136348 KB Output is correct
3 Correct 186 ms 135420 KB Output is correct
4 Correct 219 ms 138036 KB Output is correct
5 Correct 202 ms 133972 KB Output is correct
6 Correct 81 ms 115796 KB Output is correct
7 Correct 78 ms 115528 KB Output is correct
8 Correct 66 ms 113232 KB Output is correct
9 Correct 204 ms 130900 KB Output is correct
10 Correct 203 ms 131156 KB Output is correct
11 Correct 212 ms 131412 KB Output is correct
12 Correct 172 ms 127060 KB Output is correct
13 Correct 196 ms 136788 KB Output is correct
14 Incorrect 44 ms 110584 KB Output isn't correct
15 Halted 0 ms 0 KB -