oj.uz

Submission #1036890

# Submission time Handle Problem Language Result Execution time Memory
1036890 2024-07-27T19:04:58 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 375 ms 279908 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,dis[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;
	zr[z]=1;
	for(auto i:v[z]){
		if(par[z]!=i){
			par[i]=z;
			dis[i]=dis[z]+1;
			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<pair<int,int>>s[sz];
	pair<int,int> get(int id,int L,int R,int l){
		if(L+1==R)
			return (s[id].size())?*s[id].rbegin():make_pair(0,0);
		int mid=(L+R)>>1;
		pair<int,int>res;
		if(l<mid)
			res=get(id<<1,L,mid,l);
		else
			res=get((id<<1)+1,mid,R,l);
		return max(((s[id].size())?*s[id].rbegin():make_pair(0,0)),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({dis[x],x});
			else
				s[id].erase({dis[x],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;
			auto fake=gg.get(1,1,n+1,st[x]);
			int p=fake.sc;
			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);
			auto fake=gg.get(1,1,n+1,st[x]);
			int p=fake.sc;
			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 219 ms 138552 KB Output is correct
2 Correct 190 ms 136480 KB Output is correct
3 Correct 195 ms 135232 KB Output is correct
4 Correct 226 ms 138068 KB Output is correct
5 Correct 217 ms 133968 KB Output is correct
6 Correct 87 ms 115796 KB Output is correct
7 Correct 90 ms 115632 KB Output is correct
8 Correct 66 ms 113232 KB Output is correct
9 Correct 212 ms 130900 KB Output is correct
10 Correct 215 ms 131408 KB Output is correct
11 Correct 218 ms 131240 KB Output is correct
12 Correct 190 ms 127056 KB Output is correct
13 Correct 200 ms 136808 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 110672 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 293 ms 279908 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 375 ms 271968 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 219 ms 138552 KB Output is correct
2 Correct 190 ms 136480 KB Output is correct
3 Correct 195 ms 135232 KB Output is correct
4 Correct 226 ms 138068 KB Output is correct
5 Correct 217 ms 133968 KB Output is correct
6 Correct 87 ms 115796 KB Output is correct
7 Correct 90 ms 115632 KB Output is correct
8 Correct 66 ms 113232 KB Output is correct
9 Correct 212 ms 130900 KB Output is correct
10 Correct 215 ms 131408 KB Output is correct
11 Correct 218 ms 131240 KB Output is correct
12 Correct 190 ms 127056 KB Output is correct
13 Correct 200 ms 136808 KB Output is correct
14 Incorrect 45 ms 110672 KB Output isn't correct
15 Halted 0 ms 0 KB -