oj.uz

답안 #405689

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405689 2021-05-16T18:17:58 Z Pyqe Arboras (RMI20_arboras) C++11
100 / 100
 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);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 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

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 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

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 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

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 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