Submission #405689

#	Time	Username	Problem	Language	Result	Execution time	Memory
405689		Pyqe	Arboras (RMI20_arboras)	C++11	100 / 100	2000 ms	45928 KiB

arboras

#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 (stderr)

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

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