| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 635443 |
2022-08-26T09:18:29 Z |
Mahdi |
Sumtree (INOI20_sumtree) |
C++17 |
|
3000 ms |
46356 KB |
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+5, NN=3e5+5, M=1e9+7;
int ans, q, n, r, st[N], fn[N], siz[N], num[N], ss[N];
int f[N+NN], rf[N+NN];
vector<int>g[N];
int tav(int a, int b){
int res=1;
while(b){
if(b&1)
res=1LL*res*a%M;
a=1LL*a*a%M;
b>>=1;
}
return res;
}
int C(int x, int y){
//cout<<"fuck : "<<f[x]<<", "<<rf[y]<<", "<<rf[x-y]<<'\n';
ll res=1LL*f[x]*rf[y]%M;
res=res*rf[x-y]%M;
return res;
}
void pre(){
f[0]=1;
for(int i=1;i<N+NN;++i)
f[i]=1LL*f[i-1]*i%M;
rf[N+NN-1]=tav(f[N+NN-1], M-2);
for(int i=N+NN-2;i>=0;--i)
rf[i]=1LL*(i+1)*rf[i+1]%M;
}
struct seg_tree{
int sz, h[3*N], lz[3*N], a[3*N], b[3*N];
vector<int>ve;
vector<pii>ev;
seg_tree(){
sz=1;
while(sz<n)
sz<<=1;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(lz, 0, sizeof(lz));
fill(h, h+2*sz, 1);
}
int suma(int x, int lx, int rx, int l, int r){
//cout<<"\n"<<x<<", "<<a[x]<<", "<<lx<<", "<<rx<<", "<<l<<", "<<r;
if(lx>=r || rx<=l)
return 0;
//cout<<"\nwtf : \n";
if(lx>=l && rx<=r)
return a[x];
//cout<<"comon ";
int m=(lx+rx)/2;
return suma(2*x+1, lx, m, l, r)+suma(2*x+2, m, rx, l, r);
}
void adda(int x, int v){
x+=sz-1;
a[x]+=v;
while(x){
--x;
x/=2;
a[x]+=v;
}
}
int sumb(int x, int lx, int rx, int l, int r){
if(lx>=r || rx<=l)
return 0;
if(lx>=l && rx<=r)
return b[x];
int m=(lx+rx)/2;
return sumb(2*x+1, lx, m, l, r)+sumb(2*x+2, m, rx, l, r);
}
void addb(int x, int v){
x+=sz-1;
b[x]+=v;
while(x){
--x;
x/=2;
b[x]+=v;
}
}
void add(int x, int lx, int rx, int l, int r, int t){
if(lx>=r || rx<=l)
return;
if(lx>=l && rx<=r){
h[x]+=t;
lz[x]+=t;
return;
}
int m=(lx+rx)/2;
h[2*x+1]+=lz[x];
lz[2*x+1]+=lz[x];
h[2*x+2]+=lz[x];
lz[2*x+2]+=lz[x];
lz[x]=0;
add(2*x+1, lx, m, l, r, t);
add(2*x+2, m, rx, l, r, t);
h[x]=-max(-h[2*x+1], -h[2*x+2]);
}
void add(int l, int r, int t){
add(0, 0, sz, l, r, t);
}
int min(int x, int lx, int rx, int i){
if(lx==rx-1)
return h[x];
int m=(lx+rx)/2;
h[2*x+1]+=lz[x];
lz[2*x+1]+=lz[x];
h[2*x+2]+=lz[x];
lz[2*x+2]+=lz[x];
lz[x]=0;
if(i<m)
return min(2*x+1, lx, m, i);
return min(2*x+2, m, rx, i);
}
void opr(int x, int lx, int rx, int r){
if(lx>=r)
return;
if(rx<=r){
ve.push_back(x);
ev.push_back({lx, rx});
return;
}
int m=(lx+rx)/2;
h[2*x+1]+=lz[x];
lz[2*x+1]+=lz[x];
h[2*x+2]+=lz[x];
lz[2*x+2]+=lz[x];
lz[x]=0;
opr(2*x+2, m, rx, r);
opr(2*x+1, lx, m, r);
}
int fr(int x, int lx, int rx, int val){
if(lx+1==rx){
if(h[x]>=val)
return lx;
return rx;
}
int m=(lx+rx)/2;
h[2*x+1]+=lz[x];
lz[2*x+1]+=lz[x];
h[2*x+2]+=lz[x];
lz[2*x+2]+=lz[x];
lz[x]=0;
if(h[2*x+2]>=val)
return fr(2*x+1, lx, m, val);
return fr(2*x+2, m, rx, val);
}
int par(int u){
opr(0, 0, sz, u+1);
int hh=min(0, 0, sz, u);
for(int i=0;i<ve.size();++i){
if(ve[i]<hh)
return fr(ve[i], ev[i].F, ev[i].S, hh);
}
return 0;
}
};
void dfs(int &tm, const int &v, const int &p=-1){
st[v]=tm++;
ss[v]=1;
for(int u: g[v]){
if(u!=p){
dfs(tm, u, v);
ss[v]+=ss[u];
}
}
fn[v]=tm;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
pre();
cin>>n>>r;
for(int i=0;i<n-1;++i){
int u, v;
cin>>u>>v;
g[--u].push_back(--v);
}
int tm=0;
dfs(tm, 0);
seg_tree A;
ans=C(r+n-1, n-1);
cout<<ans<<'\n';
siz[0]=n;
num[0]=r;
cin>>q;
while(q--){
int t, u;
cin>>t>>u;
--u;
if(t==1){
int v;
cin>>v;
int w=A.par(u);
//cout<<w<<'\n';
A.add(st[u], fn[u], 1);
ans=1LL*ans*tav(C(num[w]+siz[w]-1, siz[w]-1), M-2)%M;
//cout<<ans<<'\n';
siz[u]=ss[u]-A.suma(0, 0, A.sz, st[u], fn[u]);
//cout<<" : "<<ss[u]<<' '<<", "<<st[u]<<", "<<fn[u]<<' '<<siz[u]<<'\n';
A.adda(u, siz[u]);
siz[w]-=siz[u];
A.adda(w, -siz[u]);
num[u]=v-A.sumb(0, 0, A.sz, st[u], fn[u]);
A.addb(u, num[u]);
num[w]-=num[u];
A.addb(w, -num[u]);
ans=1LL*ans*C(num[w]+siz[w]-1, siz[w]-1)%M;
ans=1LL*ans*C(num[u]+siz[u]-1, siz[u]-1)%M;
}
else{
A.add(st[u], fn[u], -1);
int w=A.par(u);
ans=1LL*ans*tav(C(num[w]+siz[w]-1, siz[w]-1), M-2)%M;
ans=1LL*ans*tav(C(num[u]+siz[u]-1, siz[u]-1), M-2)%M;
A.adda(u, -siz[u]);
siz[w]+=siz[u];
A.adda(w, siz[u]);
A.addb(u, -num[u]);
num[w]+=num[u];
A.addb(w, num[u]);
ans=1LL*ans*C(num[w]+siz[w]-1, siz[w]-1)%M;
}
cout<<ans<<'\n';
}
}
/*
3 2
1 2
2 3
1
1 2 1
*/
Compilation message
Main.cpp: In member function 'int seg_tree::par(int)':
Main.cpp:172:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for(int i=0;i<ve.size();++i){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
22604 KB |
Output is correct |
| 2 |
Correct |
71 ms |
22612 KB |
Output is correct |
| 3 |
Correct |
66 ms |
22572 KB |
Output is correct |
| 4 |
Correct |
70 ms |
22660 KB |
Output is correct |
| 5 |
Correct |
74 ms |
22988 KB |
Output is correct |
| 6 |
Correct |
16 ms |
18416 KB |
Output is correct |
| 7 |
Correct |
14 ms |
18388 KB |
Output is correct |
| 8 |
Correct |
15 ms |
18440 KB |
Output is correct |
| 9 |
Correct |
75 ms |
22968 KB |
Output is correct |
| 10 |
Correct |
70 ms |
22964 KB |
Output is correct |
| 11 |
Correct |
71 ms |
23496 KB |
Output is correct |
| 12 |
Correct |
72 ms |
24424 KB |
Output is correct |
| 13 |
Correct |
65 ms |
22272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
18260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
85 ms |
46356 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3064 ms |
30564 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
22604 KB |
Output is correct |
| 2 |
Correct |
71 ms |
22612 KB |
Output is correct |
| 3 |
Correct |
66 ms |
22572 KB |
Output is correct |
| 4 |
Correct |
70 ms |
22660 KB |
Output is correct |
| 5 |
Correct |
74 ms |
22988 KB |
Output is correct |
| 6 |
Correct |
16 ms |
18416 KB |
Output is correct |
| 7 |
Correct |
14 ms |
18388 KB |
Output is correct |
| 8 |
Correct |
15 ms |
18440 KB |
Output is correct |
| 9 |
Correct |
75 ms |
22968 KB |
Output is correct |
| 10 |
Correct |
70 ms |
22964 KB |
Output is correct |
| 11 |
Correct |
71 ms |
23496 KB |
Output is correct |
| 12 |
Correct |
72 ms |
24424 KB |
Output is correct |
| 13 |
Correct |
65 ms |
22272 KB |
Output is correct |
| 14 |
Incorrect |
14 ms |
18260 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
