oj.uz

Submission #635491

# Submission time Handle Problem Language Result Execution time Memory
635491 2022-08-26T10:30:27 Z Mahdi Sumtree (INOI20_sumtree) C++17
10 / 100
 210 ms 25644 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], cmo;
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){
    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){
        if(lx>=r || rx<=l)
            return 0;
        if(lx>=l && rx<=r)
            return a[x];
        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=st[x];
        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=st[x];
        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){
        u=st[u];
        opr(0, 0, sz, u+1);
        int hh=min(0, 0, sz, u);
        int res=0;
        for(int i=0;i<ve.size();++i){
            if(h[ve[i]]<hh){
                res=fr(ve[i], ev[i].F, ev[i].S, hh);
                break;
            }
        }
        ve.clear();
        ev.clear();
        return res;
    }
};

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;
}

void ud(const int &v){
    if(num[v]<0)
        --cmo;
    else
        ans=1LL*ans*tav(C(num[v]+siz[v]-1, siz[v]-1), M-2)%M;
}

void du(const int &v){
    if(num[v]<0)
        ++cmo;
    else
        ans=1LL*ans*C(num[v]+siz[v]-1, siz[v]-1)%M;
}

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);
            A.add(st[u], fn[u], 1);
            ud(w);
            siz[u]=ss[u]-A.suma(0, 0, A.sz, st[u], fn[u]);
            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]);
            du(w);
            du(u);
        }
        else{
            A.add(st[u], fn[u], -1);
            int w=A.par(u);
            ud(w);
            ud(u);
            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]);
            du(u);
        }
        if(cmo==0)
            cout<<ans<<'\n';
        else
            cout<<0<<'\n';
    }
}

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){
      |                     ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 22936 KB Output is correct
2 Correct 76 ms 22988 KB Output is correct
3 Correct 80 ms 22968 KB Output is correct
4 Correct 77 ms 23008 KB Output is correct
5 Correct 84 ms 23372 KB Output is correct
6 Correct 15 ms 18344 KB Output is correct
7 Correct 16 ms 18336 KB Output is correct
8 Correct 14 ms 18388 KB Output is correct
9 Correct 70 ms 23244 KB Output is correct
10 Correct 68 ms 23224 KB Output is correct
11 Correct 72 ms 23736 KB Output is correct
12 Correct 76 ms 24772 KB Output is correct
13 Correct 83 ms 22564 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 22936 KB Output is correct
2 Correct 76 ms 22988 KB Output is correct
3 Correct 80 ms 22968 KB Output is correct
4 Correct 77 ms 23008 KB Output is correct
5 Correct 84 ms 23372 KB Output is correct
6 Correct 15 ms 18344 KB Output is correct
7 Correct 16 ms 18336 KB Output is correct
8 Correct 14 ms 18388 KB Output is correct
9 Correct 70 ms 23244 KB Output is correct
10 Correct 68 ms 23224 KB Output is correct
11 Correct 72 ms 23736 KB Output is correct
12 Correct 76 ms 24772 KB Output is correct
13 Correct 83 ms 22564 KB Output is correct
14 Incorrect 17 ms 18344 KB Output isn't correct
15 Halted 0 ms 0 KB -