oj.uz

Submission #1036878

# Submission time Handle Problem Language Result Execution time Memory
1036878 2024-07-27T18:41:04 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 364 ms 277984 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]);
			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]);
			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 205 ms 137556 KB Output is correct
2 Correct 192 ms 135644 KB Output is correct
3 Correct 189 ms 134480 KB Output is correct
4 Correct 203 ms 137296 KB Output is correct
5 Correct 203 ms 133200 KB Output is correct
6 Correct 81 ms 115776 KB Output is correct
7 Correct 82 ms 115432 KB Output is correct
8 Correct 65 ms 113232 KB Output is correct
9 Correct 207 ms 130128 KB Output is correct
10 Correct 206 ms 130388 KB Output is correct
11 Correct 209 ms 130408 KB Output is correct
12 Correct 173 ms 126288 KB Output is correct
13 Correct 187 ms 136016 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 110720 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 294 ms 277984 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 364 ms 269904 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 205 ms 137556 KB Output is correct
2 Correct 192 ms 135644 KB Output is correct
3 Correct 189 ms 134480 KB Output is correct
4 Correct 203 ms 137296 KB Output is correct
5 Correct 203 ms 133200 KB Output is correct
6 Correct 81 ms 115776 KB Output is correct
7 Correct 82 ms 115432 KB Output is correct
8 Correct 65 ms 113232 KB Output is correct
9 Correct 207 ms 130128 KB Output is correct
10 Correct 206 ms 130388 KB Output is correct
11 Correct 209 ms 130408 KB Output is correct
12 Correct 173 ms 126288 KB Output is correct
13 Correct 187 ms 136016 KB Output is correct
14 Incorrect 44 ms 110720 KB Output isn't correct
15 Halted 0 ms 0 KB -