| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1110204 |
2024-11-09T02:01:32 Z |
modwwe |
Arboras (RMI20_arboras) |
C++17 |
|
981 ms |
65096 KB |
#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)
{
assert(abs(x)<=mod2);
assert(abs(y)<=mod2);
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[100007], heavy[100007];
vector<int> v[100007];
int ou[100007], st[18][100007];
multiset<int> f[100007];
int c[100007], head[100007];
struct seg
{
int t[400007],t2[400007],sz[400007],t3[400007];
void ff(int x)
{
for(int i=x*2; i<=x*2+1; i++)
if(t2[x]!=-1)
{
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]==-1)t3[i]=add(t3[i],t3[x]);
else t2[i]=add(t2[i],t3[x]);
}
t3[x]=0;
t2[x]=-1;
}
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]!=-1||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]!=-1)t2[node]=add(t2[node],x);
else t3[node]=add(t3[node],x);
return;
}
int mid=l+r>>1;
if(t2[node]!=-1||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]);
}
} segtree;
struct seg2
{
int t[400007],t2[400007];
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%mod2);
return;
}
segtree.upd(1,1,n,pos[head[x]],pos[x],cost%mod2);
x=head[x];
while(heavy[st[0][x]]!=x&&st[0][x]>=y)
{
upd_pos2(st[0][x],x,cost);
x=st[0][x];
}
upd_hld(st[0][x],y,cost);
}
void upd(int x,int y)
{
seg2.upd(1,1,n,pos[x],ou[x],y);
int maxx=seg2.get(1,1,n,pos[x],ou[x]);
segtree.upd2(1,1,n,pos[x],ou[x],y);
int kkk=y;
y=x;
for(int i=17; 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<18; i++)
for(int j=1; j<=n; j++)
st[i][j]=st[i-1][st[i-1][j]];
s4=0;
for(int i=1; i<=n; i++)
segtree.t2[i]=-1;
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
}
}
Compilation message
arboras.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
35 | main()
| ^~~~
arboras.cpp: In member function 'void seg::build(long long int, long long int, long long int)':
arboras.cpp:78:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | 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:92:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | 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:108:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
108 | 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:135:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
135 | 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:145:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
145 | int mid=l+r>>1;
| ~^~
arboras.cpp: In function 'long long int dfs(long long int)':
arboras.cpp:159:14: warning: unused variable 'g' [-Wunused-variable]
159 | for(auto g:v[x])
| ^
arboras.cpp: In function 'void upd(long long int, long long int)':
arboras.cpp:223:9: warning: unused variable 'kkk' [-Wunused-variable]
223 | 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:39:9: note: in expansion of macro 'fin'
39 | 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:40:9: note: in expansion of macro 'fou'
40 | fou(task);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
31312 KB |
Output is correct |
| 2 |
Correct |
7 ms |
31312 KB |
Output is correct |
| 3 |
Correct |
8 ms |
31484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
695 ms |
49688 KB |
Output is correct |
| 2 |
Correct |
502 ms |
48576 KB |
Output is correct |
| 3 |
Correct |
577 ms |
49048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
915 ms |
54392 KB |
Output is correct |
| 2 |
Correct |
405 ms |
64708 KB |
Output is correct |
| 3 |
Correct |
981 ms |
53900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
31312 KB |
Output is correct |
| 2 |
Correct |
7 ms |
31312 KB |
Output is correct |
| 3 |
Correct |
8 ms |
31484 KB |
Output is correct |
| 4 |
Correct |
695 ms |
49688 KB |
Output is correct |
| 5 |
Correct |
502 ms |
48576 KB |
Output is correct |
| 6 |
Correct |
577 ms |
49048 KB |
Output is correct |
| 7 |
Correct |
915 ms |
54392 KB |
Output is correct |
| 8 |
Correct |
405 ms |
64708 KB |
Output is correct |
| 9 |
Correct |
981 ms |
53900 KB |
Output is correct |
| 10 |
Correct |
862 ms |
56648 KB |
Output is correct |
| 11 |
Correct |
469 ms |
64452 KB |
Output is correct |
| 12 |
Correct |
902 ms |
53816 KB |
Output is correct |
| 13 |
Correct |
417 ms |
62632 KB |
Output is correct |
| 14 |
Correct |
320 ms |
65096 KB |
Output is correct |
