Submission #1110074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110074		modwwe	Arboras (RMI20_arboras)	C++17	0 / 100	1065 ms	51784 KiB

arboras

#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC optimize("conserve-stack")
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf = 1e18;
const int mod2 = 1e9 + 7;
const int  mod1 = 998244353;
const ll base=67;
int add(int x,int y)
{
    if(x+y>=mod2) x-=mod2;
    if(x+y<0) x+=mod2;
    return x+y;
}
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,t,lim,w,l,r;
int kk;
int el = 19;
main()
{
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo();
    // checktime
}
int pos[100001], heavy[100001];
vector<int> v[100001];
int ou[100001], st[17][100001];
multiset<int> f[100001];
int c[100001], head[100001];
struct seg
{
    int t[400001],t2[400001],sz[400001],t3[400001];
    void ff(int x)
    {
        if(t2[x]!=0&&t3[x]!=0)
        {
            assert(0);
        }
        for(int i=x*2; i<=x*2+1; i++)
            if(t2[x]!=0)
            {
                t[i]=t2[x]*sz[i]%mod2;
                t2[i]=t2[x];
                t3[i]=0;
            }
            else
            {
                t[i]=add(t[i],t3[x]*sz[i]%mod2);
                if(t2[i]==0)t3[i]=add(t3[i],t3[x]);
                else t2[i]=add(t2[i],t3[x]);
            }
        t3[x]=0;
        t2[x]=0;
    }
    void build(int node,int l,int r)
    {
        sz[node]=r-l+1;
        if(l==r) return;
        int mid=l+r>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
    }
    void upd(int node,int l,int r,int l1,int r1,int x)
    {
        if(l>r1||r<l1) return;
        if(l>=l1&&r<=r1)
        {
            t[node]=sz[node]*x%mod2;
            t2[node]=x%mod2;
            t3[node]=0;
            return;
        }
        int mid=l+r>>1;
        if(t2[node]!=0||t3[node]!=0) ff(node);
        upd(node<<1,l,mid,l1,r1,x);
        upd(node<<1|1,mid+1,r,l1,r1,x);
        t[node]=add(t[node<<1],t[node<<1|1]);
    }
    void upd2(int node,int l,int r,int l1,int r1,int x)
    {
        if(l>r1||r<l1) return;
        if(l>=l1&&r<=r1)
        {
            t[node]=add(t[node],sz[node]*x%mod2);
            if(t2[node]!=0)t2[node]=add(t2[node],x);
            else t3[node]=add(t3[node],x);
            return;
        }
        int mid=l+r>>1;
        if(t2[node]!=0||t3[node]!=0) ff(node);
        upd2(node<<1,l,mid,l1,r1,x);
        upd2(node<<1|1,mid+1,r,l1,r1,x);
        t[node]=add(t[node<<1],t[node<<1|1]);
    }
    int get(int node,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1) return 0;
        if(l>=l1&&r<=r1) return t[node];
        int mid=l+r>>1;
        if(t2[node]!=0||t3[node]!=0) ff(node);
        return get(node<<1,l,mid,l1,r1)+get(node<<1|1,mid+1,r,l1,r1);
    }
} segtree;
struct seg2
{
    int t[400001],t2[400001];
    void ff(int x)
    {
        for(int i=x*2; i<=x*2+1; i++)
            t[i]=t[i]+t2[x],
                 t2[i]=t2[i]+t2[x];
        t2[x]=0;
    }
    void upd(int node,int l,int r,int l1,int r1,int x)
    {
        if(l>r1||r<l1) return;
        if(l>=l1&&r<=r1)
        {
            t[node]+=x;
            t2[node]+=x;
            return;
        }
        if(t2[node]!=0)ff(node);
        int mid=l+r>>1;
        upd(node<<1,l,mid,l1,r1,x);
        upd(node<<1|1,mid+1,r,l1,r1,x);
        t[node]=max(t[node<<1],t[node<<1|1]);
    }
    int get(int node,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1)return 0;
        if(l>=l1&&r<=r1) return t[node];
        if(t2[node]!=0) ff(node);
        int mid=l+r>>1;
        return max(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1));
    }
} seg2;
int dfs(int x)
{
    int sz=1;
    int mxz=0;
    for(auto f:v[x])
    {
        int s=dfs(f);
        sz+=s;
        if(s>mxz) mxz=s,heavy[x]=f;
    }
    for(auto g:v[x])
        f[x].insert(0);
    return sz;
}
void des(int x,int y)
{
    head[x]=y;
    pos[x]=++dem;
    if(heavy[x]!=0)des(heavy[x],y);
    for(auto f:v[x])
        if(f!=heavy[x])
            des(f,f);
    ou[x]=dem;
}
int check(int x)
{
    return seg2.get(1,1,n,pos[x],ou[x]);
}
int cc(int x)
{
    if(f[x].size()==0)return 0;
    return *f[x].rbegin()%mod2;
}
void upd_pos2(int x,int y,int cost)
{
    if(x==0) return;
    s4=add(s4,-cc(x));
    int kk=seg2.get(1,1,n,pos[x],pos[x]);
    if(y!=heavy[x])
    {
        auto it=f[x].lower_bound(c[y]);
        f[x].erase(it);
        c[y]=cost-kk;
        f[x].insert(c[y]);
    }
    s4=add(s4,cc(x));
    int s=0;
    if(f[x].size()>=2)s=*next(f[x].rbegin());
    if(heavy[x]!=0)s=max(s,check(heavy[x])-kk);
    else s=check(x)-kk;
    segtree.upd(1,1,n,pos[x],pos[x],(s+kk)%mod2);
}
void upd_hld(int x,int y,int cost)
{
    if(x<y)return;
    if(head[x]<=y)
    {
        segtree.upd(1,1,n,pos[y],pos[x],cost);
        return;
    }
    segtree.upd(1,1,n,pos[head[x]],pos[x],cost);
    upd_pos2(st[0][head[x]],head[x],cost);
    upd_hld(st[1][head[x]],y,cost);
}
void upd(int x,int y)
{
     //cout<<x<<" "<<y<<"\n";
    seg2.upd(1,1,n,pos[x],ou[x],y);
    int maxx=seg2.get(1,1,n,pos[x],ou[x]);
    // cout<<segtree.t[1],debug
    segtree.upd2(1,1,n,pos[x],ou[x],y);
    int kkk=y;
    y=x;
    for(int i=16; i>=0; --i)
        if(check(st[i][x])==maxx)
            x=st[i][x];
    if(x==0)x=1;
    upd_hld(y,x,maxx);
    upd_pos2(y,heavy[y],0);
    upd_pos2(st[0][x],x,maxx);
}
void phongbeo()
{
    cin>>n;
    for(int i=2; i<=n; i++)
        cin>>l,l++,v[l].pb(i),st[0][i]=l;
    dfs(1);
    des(1,1);
    pos[0]=1;
    segtree.build(1,1,n);
    ou[0]=dem;
    for(int i=1; i<17; i++)
        for(int j=1; j<=n; j++)
            st[i][j]=st[i-1][st[i-1][j]];
    s4=0;
    for(int i=2; i<=n; i++)
    {
        cin>>l;
        s4=add(s4,-(ou[i]-pos[i]+1)*l%mod2);
        upd(i,l);
    }
    cout<<add(s4,segtree.t[1]),down
        cin>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>l>>r;
        l++;
        s4=add(s4,-(ou[l]-pos[l]+1)*r%mod2);
        upd(l,r);
        cout<<add(s4,segtree.t[1]),down
    }
}
/*
3
0 1
0 0
1
1 1
*/

Compilation message (stderr)

arboras.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main()
      | ^~~~
arboras.cpp: In member function 'void seg::build(long long int, long long int, long long int)':
arboras.cpp:80:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int mid=l+r>>1;
      |                 ~^~
arboras.cpp: In member function 'void seg::upd(long long int, long long int, long long int, long long int, long long int, long long int)':
arboras.cpp:94:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         int mid=l+r>>1;
      |                 ~^~
arboras.cpp: In member function 'void seg::upd2(long long int, long long int, long long int, long long int, long long int, long long int)':
arboras.cpp:110:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         int mid=l+r>>1;
      |                 ~^~
arboras.cpp: In member function 'long long int seg::get(long long int, long long int, long long int, long long int, long long int)':
arboras.cpp:120:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |         int mid=l+r>>1;
      |                 ~^~
arboras.cpp: In member function 'void seg2::upd(long long int, long long int, long long int, long long int, long long int, long long int)':
arboras.cpp:145:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  145 |         int mid=l+r>>1;
      |                 ~^~
arboras.cpp: In member function 'long long int seg2::get(long long int, long long int, long long int, long long int, long long int)':
arboras.cpp:155:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  155 |         int mid=l+r>>1;
      |                 ~^~
arboras.cpp: In function 'long long int dfs(long long int)':
arboras.cpp:169:14: warning: unused variable 'g' [-Wunused-variable]
  169 |     for(auto g:v[x])
      |              ^
arboras.cpp: In function 'void upd(long long int, long long int)':
arboras.cpp:230:9: warning: unused variable 'kkk' [-Wunused-variable]
  230 |     int kkk=y;
      |         ^~~
arboras.cpp: In function 'int main()':
arboras.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
arboras.cpp:37:9: note: in expansion of macro 'fin'
   37 |         fin(task);
      |         ^~~
arboras.cpp:14:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define fou(x) freopen(x".ans","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
arboras.cpp:38:9: note: in expansion of macro 'fou'
   38 |         fou(task);
      |         ^~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 31
• Subtask 4: 0 / 45