| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 405689 |
2021-05-16T18:17:58 Z |
Pyqe |
Arboras (RMI20_arboras) |
C++11 |
|
2000 ms |
45928 KB |
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long dv=1e9+7,inf=1e18;
long long n,sbt[100069],an[100069],dh[100069],fh[100069],pr[100069],peu[100069],z=0;
vector<long long> al[100069];
struct segtree
{
long long l,r,mx,mx2,c,sm,lz,lz2,lz3;
pair<long long,long long> opt[2],mne;
segtree *p[2];
void bd(long long lh,long long rh)
{
long long ii;
l=lh;
r=rh;
mx=0;
mx2=0;
for(ii=0;ii<2;ii++)
{
opt[ii]={0,0};
}
mne={0,l};
c=0;
sm=0;
lz=0;
lz2=-inf;
lz3=-inf;
if(l<r)
{
long long md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
}
}
void ad(long long ky,long long w,long long w2)
{
if(ky==1)
{
long long ii;
mx+=w;
mx2+=w;
for(ii=0;ii<2;ii++)
{
opt[ii].fr+=w;
}
mne.fr+=w;
sm=(sm+w%dv*c)%dv;
lz+=w;
lz2+=w;
lz3+=w;
}
else if(ky==2)
{
if(w>=0)
{
mx=w;
lz2=w;
}
}
else if(ky==3)
{
if(w>=0)
{
mx2=w;
sm=w%dv*c%dv;
lz3=w;
}
}
else if(ky==4)
{
long long ii;
z=(z+dv-(opt[0].fr+max(opt[1].fr,mx2))%dv)%dv;
for(ii=0;ii<2;ii++)
{
if(opt[ii].sc==w2)
{
opt[ii].fr=0;
if(!ii)
{
swap(opt[0],opt[1]);
}
break;
}
}
opt[1]=max(opt[1],min(opt[0],{w,w2}));
opt[0]=max(opt[0],{w,w2});
z=(z+opt[0].fr+max(opt[1].fr,mx2))%dv;
if(opt[1].fr>=mx2)
{
mne.fr=opt[1].fr;
c=0;
sm=0;
}
else
{
mne.fr=inf;
c=1;
sm=mx2%dv;
}
}
else
{
z=(z+mx2+dv-opt[1].fr%dv)%dv;
mne.fr=inf;
c=1;
sm=mx2%dv;
}
}
void blc()
{
long long ii;
for(ii=0;ii<2;ii++)
{
p[ii]->ad(1,lz,0);
p[ii]->ad(2,lz2,0);
p[ii]->ad(3,lz3,0);
}
lz=0;
lz2=-inf;
lz3=-inf;
}
void ud(long long ky,long long lh,long long rh,long long w,long long w2)
{
if(l>rh||r<lh);
else if(l>=lh&&r<=rh)
{
ad(ky,w,w2);
}
else
{
long long ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ud(ky,lh,rh,w,w2);
}
mx=max(p[0]->mx,p[1]->mx);
mne=min(p[0]->mne,p[1]->mne);
c=p[0]->c+p[1]->c;
sm=(p[0]->sm+p[1]->sm)%dv;
}
}
long long qr(long long ky,long long lh,long long rh)
{
if(l>rh||r<lh)
{
return 0;
}
else if(l>=lh&&r<=rh)
{
if(ky==1)
{
return mx;
}
else if(ky==2)
{
return c;
}
else
{
return sm;
}
}
else
{
blc();
if(ky==1)
{
return max(p[0]->qr(ky,lh,rh),p[1]->qr(ky,lh,rh));
}
else if(ky==2)
{
return p[0]->qr(ky,lh,rh)+p[1]->qr(ky,lh,rh);
}
else
{
return (p[0]->qr(ky,lh,rh)+p[1]->qr(ky,lh,rh))%dv;
}
}
}
long long bl(long long lh,long long rh,long long w)
{
if(l>rh||r<lh)
{
return max(l,lh);
}
else if(l>=lh&&r<=rh)
{
if(mx<w)
{
return l;
}
else if(l==r)
{
return l+1;
}
else
{
blc();
return p[p[1]->mx>=w]->bl(lh,rh,w);
}
}
else
{
long long k;
blc();
k=p[1]->bl(lh,rh,w);
if(k>max(p[1]->l,lh))
{
return k;
}
else
{
return p[0]->bl(lh,rh,w);
}
}
}
pair<long long,long long> qr2(long long lh,long long rh)
{
if(l>rh||r<lh)
{
return {inf,-1};
}
else if(l>=lh&&r<=rh)
{
return mne;
}
else
{
blc();
return min(p[0]->qr2(lh,rh),p[1]->qr2(lh,rh));
}
}
}
sg;
void bd(long long x)
{
long long i,sz=al[x].size(),l,e;
pair<long long,long long> mxe={0,-1};
sbt[x]=1;
an[x]=x;
fh[x]=dh[x];
for(i=0;i<sz;i++)
{
l=al[x][i];
dh[l]=dh[x]+1;
pr[l]=x;
bd(l);
sbt[x]+=sbt[l];
mxe=max(mxe,{sbt[l],i});
}
e=mxe.sc;
if(e+1)
{
swap(al[x][0],al[x][e]);
l=al[x][0];
an[l]=x;
fh[x]=fh[l];
}
}
void bd2(long long x)
{
long long i,sz=al[x].size(),l;
an[x]=an[an[x]];
n++;
peu[x]=n;
for(i=0;i<sz;i++)
{
l=al[x][i];
bd2(l);
}
}
void pth(long long x,long long w)
{
long long k,l=x,p,lb,rb;
pair<long long,long long> tmp;
for(p=pr[x];p;p=pr[an[p]])
{
if(an[p]!=an[l])
{
sg.ud(4,peu[p],peu[p],w,l);
}
k=sg.bl(peu[an[p]],peu[p],w);
lb=max(k-1,peu[an[p]]);
rb=peu[p]-(an[p]!=an[l]);
for(;1;)
{
tmp=sg.qr2(lb,rb);
if(tmp.fr>=w)
{
break;
}
sg.ud(5,tmp.sc,tmp.sc,0,0);
}
z=(z+w%dv*sg.qr(2,lb,rb)+dv-sg.qr(3,lb,rb))%dv;
sg.ud(2,k,peu[p],w,0);
sg.ud(3,lb,rb,w,0);
if(k>peu[an[p]])
{
break;
}
l=an[p];
}
}
void ud(long long x,long long w)
{
sg.ud(1,peu[x],peu[x]+sbt[x]-1,w,0);
pth(x,sg.qr(1,peu[x],peu[x]));
}
int main()
{
long long t,rr,i,k,l;
scanf("%lld",&n);
for(i=2;i<=n;i++)
{
scanf("%lld",&k);
k++;
al[k].push_back(i);
}
bd(1);
n=0;
bd2(1);
sg.bd(1,n);
for(i=2;i<=n;i++)
{
scanf("%lld",&k);
ud(i,k);
}
scanf("%lld",&t);
for(rr=0;rr<=t;rr++)
{
if(rr)
{
scanf("%lld%lld",&k,&l);
k++;
ud(k,l);
}
printf("%lld\n",z);
}
}
Compilation message
arboras.cpp: In function 'int main()':
arboras.cpp:340:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
340 | scanf("%lld",&n);
| ~~~~~^~~~~~~~~~~
arboras.cpp:343:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
343 | scanf("%lld",&k);
| ~~~~~^~~~~~~~~~~
arboras.cpp:353:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
353 | scanf("%lld",&k);
| ~~~~~^~~~~~~~~~~
arboras.cpp:356:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
356 | scanf("%lld",&t);
| ~~~~~^~~~~~~~~~~
arboras.cpp:361:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
361 | scanf("%lld%lld",&k,&l);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
3020 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3020 KB |
Output is correct |
| 3 |
Correct |
8 ms |
3020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2000 ms |
40504 KB |
Output is correct |
| 2 |
Correct |
1043 ms |
39020 KB |
Output is correct |
| 3 |
Correct |
1053 ms |
39324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1788 ms |
42692 KB |
Output is correct |
| 2 |
Correct |
914 ms |
45488 KB |
Output is correct |
| 3 |
Correct |
1280 ms |
40900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
3020 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3020 KB |
Output is correct |
| 3 |
Correct |
8 ms |
3020 KB |
Output is correct |
| 4 |
Correct |
2000 ms |
40504 KB |
Output is correct |
| 5 |
Correct |
1043 ms |
39020 KB |
Output is correct |
| 6 |
Correct |
1053 ms |
39324 KB |
Output is correct |
| 7 |
Correct |
1788 ms |
42692 KB |
Output is correct |
| 8 |
Correct |
914 ms |
45488 KB |
Output is correct |
| 9 |
Correct |
1280 ms |
40900 KB |
Output is correct |
| 10 |
Correct |
1614 ms |
42376 KB |
Output is correct |
| 11 |
Correct |
910 ms |
45236 KB |
Output is correct |
| 12 |
Correct |
1215 ms |
40772 KB |
Output is correct |
| 13 |
Correct |
1929 ms |
44824 KB |
Output is correct |
| 14 |
Correct |
1327 ms |
45928 KB |
Output is correct |
