QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#431376#5830. 树Doqe0 2642ms253472kbC++172.5kb2024-06-05 13:59:282024-06-05 13:59:29

Judging History

你现在查看的是最新测评结果

  • [2024-06-05 13:59:29]
  • 评测
  • 测评结果:0
  • 用时:2642ms
  • 内存:253472kb
  • [2024-06-05 13:59:28]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,B=20;
int n,I,U;char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	return x*f;
}
struct node
{
	unsigned vl[N*4],u1[N*2],u2[N*2];
	int Z;
	pair<int,int>ask(int d,int k)
	{
		unsigned v1=vl[d		]-vl[d+U/2	],
		         v2=vl[d+U/2	]-vl[d+U	];
		int r =(k&U-1),z=k-r;
		if(r<U/2)
		{
			v1-=vl[d+U+z]-vl[d+k+1+U];
			v1-=vl[d+k+1]-vl[d+U/2+z];
			v2-=vl[d+U/2+z]-vl[d+U+z];
		}
		else
		{
			v1-=vl[d+z+U]-vl[d+z+U/2+U];
			v2-=vl[d+z+U/2+U]-vl[d+k+1+U];
			v2-=vl[d+k+1]-vl[d+U+z];
		}
		return make_pair((int)v1,(int)v2);
	}
	void shrink(int W)
	{
		while(Z>W)
		{
			if(Z>U)u2[Z-U]+=u2[Z];
			u1[Z]+=u2[Z];u1[Z-1]+=u1[Z];
			vl[Z]+=u1[Z];u1[Z]=u2[Z]=0;--Z;
		}
	}
	void ins(int d,int v){Z=max(Z,d),u2[d]+=v;}
}V,C;
vector<pair<int,int>>Q[N];
vector<int>to[N];
int v[N],w[N],dep[N];
long long ans[N];
void ins(int d,int v){V.ins(d,v>>I&1),C.ins(d,1);}
void shrink(int W){V.shrink(W),C.shrink(W);}
long long ask(int d,int k)
{
	auto k1=V.ask(d,k),k2=C.ask(d,k);
	return (1ll*k1.first+k2.second-k1.second)<<I;
}
int task[N*2],cnt;
namespace Z
{
	long long s[N*2],x[N];int Z;
	long long ask(int d,int k){return s[d]-s[d+k+1];}
	void shrink(int W)
	{
		while(Z>W){x[Z-1]+=x[Z];s[Z]+=x[Z];x[Z]=0;--Z;}
	}
	void ins(int d,int v){Z=max(Z,d),x[d]+=v;}
}
void pre(int u,int f,int D)
{
	task[++cnt]=u;dep[u]=D;
	for(auto k:Q[u])ans[k.second]-=Z::ask(D,min(k.first,n-D));
	Z::ins(D,w[u]);
	for(int v:to[u])pre(v,u,D+1);
	Z::shrink(D-1);
	for(auto k:Q[u])ans[k.second]+=Z::ask(D,min(k.first,n-D));
	task[++cnt]=-u;
}
int main()
{
	n=rd();for(int i=1;i<=n;++i)v[i]=rd(),w[i]=v[i]>>B<<B,v[i]-=w[i];
	for(int i=2;i<=n;++i)to[rd()].push_back(i);
	int q=rd();for(int i=1,x,k;i<=q;++i)x=rd(),q=rd(),Q[x].emplace_back(k,i); 
	pre(1,0,1);
	for(int i=0;i<B;++i)
	{
		#define mem(z) memset(V.z,0,sizeof V.z);memset(C.z,0,sizeof C.z)
		mem(vl);
		I=i,U=(1<<I+1);
		for(int i=1;i<=cnt;++i)
		{
			int u=task[i],D=dep[abs(u)];
			if(u>0)
			{
				for(auto k:Q[u])ans[k.second]-=ask(D,min(k.first,n-D));
				ins(D,v[u]);
			}
			else
			{
				u=-u;shrink(D-1);
				for(auto k:Q[u])ans[k.second]+=ask(D,min(k.first,n-D));
			}
		}
	}
	for(int i=1;i<=q;++i)cout<<ans[i]<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 26ms
memory: 103992kb

input:

2000
946347867 341162491 202762650 295215762 254064439 66267204 693162580 357612557 492940637 939526638 59775103 374919339 144042807 861369313 651043728 999024805 439554916 167782038 597475252 56704409 69846137 22185655 79439847 769194737 145071391 226046618 915359433 392527325 84982946 54584098 827...

output:

993507687

result:

wrong answer 1st numbers differ - expected: '31727996563', found: '993507687'

Test #2:

score: 0
Wrong Answer
time: 78ms
memory: 109756kb

input:

99999
792064428 473106195 799314986 65440734 948726345 442414256 280245405 873012700 466192412 899092866 283555341 657824017 963883713 793944180 767444438 105576842 542107696 580140098 65321660 381184238 584604194 397414881 861590124 309323011 217641157 120832524 303744205 961590116 110259426 380351...

output:

846597496

result:

wrong answer 1st numbers differ - expected: '2509771019', found: '846597496'

Test #3:

score: 0
Wrong Answer
time: 317ms
memory: 253472kb

input:

1000000
947727010 179844140 923847675 171881267 5552129 974443359 989307850 869400987 126992154 527448411 141137718 136124474 917813105 392020809 79012342 473860575 969007624 833563354 90169336 878445705 84352622 403307122 733751738 670851448 942399068 731541999 101293644 545785337 964751520 9168003...

output:

20837247
76467421
1073973
691818403
909636612
125674044
273720788
609036445
976527349
536868014
776339167
434536715
872679602
233193354
795678195
6650391
331421366
830498259
398292176
28590357
188596148
506164148
558450466
246673922
263108603
103850231
993531012
567705075
33889164
39283269
907138195...

result:

wrong answer 1st numbers differ - expected: '322288180595345', found: '20837247'

Test #4:

score: 0
Wrong Answer
time: 302ms
memory: 253044kb

input:

1000000
264862971 751386013 921867736 711577153 262726588 565608444 975324815 440219681 107888226 928241413 729126923 283912914 86248857 896446999 12839598 651796991 139813366 105131395 341646170 839485925 939265720 844548518 102280410 457829889 8602879 737140565 17206920 974175632 535833885 8373832...

output:

45553702
10835306
64251738
15571767
79197658
446006694
133313773
617643391
182235547
40205329
730341652
199807210
743057406
795446731
590045739
315695315
486290989
249685254
327219944
946322406
709470051
7953971
309882795
818906565
43821129
148541582
348634812
118651754
227209911
681112153
520956686...

result:

wrong answer 1st numbers differ - expected: '1437301063221', found: '45553702'

Test #5:

score: 0
Wrong Answer
time: 389ms
memory: 155872kb

input:

1000000
978606419 773027389 111265179 979476504 280718851 476857501 751854950 579263969 848569548 781051974 31782627 533831186 812822170 111553645 297770650 331144396 676977983 2236128 258203325 75591120 676466973 60056446 494411414 286185093 92474576 173276071 535648669 87210101 355790411 880267291...

output:

303451427

result:

wrong answer 1st numbers differ - expected: '2258826661', found: '303451427'

Test #6:

score: 0
Wrong Answer
time: 2642ms
memory: 179820kb

input:

1000000
952470566 585754087 120174600 401525004 458588768 5487567 31210348 446333263 231409083 521960132 457721893 866842852 925207283 16805978 4706826 99640835 619272676 136536623 459247161 308807462 633687300 717271369 23906473 865522890 173799280 424309108 719410673 118906385 110627845 730629403 ...

output:

994051214
904057442
991014390
788120198
906646521
71563042
174620909
43760580
875609574
402865267
320315079
716198149
190685967
333078113
26720867
557364187
277644219
3104092
276690929
866996908
467852673
7840503
425554649
298531179
242847413
426018723
576413176
676148373
931711821
11254324
26549939...

result:

wrong answer 3rd numbers differ - expected: '2995278795', found: '991014390'

Test #7:

score: 0
Wrong Answer
time: 2642ms
memory: 188140kb

input:

1000000
732367509 105027907 958920212 886798715 102486738 813075884 301085392 242303497 979657287 944859684 307768 438158233 561755409 740706505 791145209 283862713 828081846 771569552 59044985 600549571 191330226 438693570 36976319 810654215 220068818 771875421 740642902 839964155 206129566 2065543...

output:

148765427
401770479
784262831
912944113
835807320
139368354
174777411
634911984
161582949
786430034
108362825
242670567
75514756
262144790
622448441
167205592
696249358
64114734
245208406
108986628
701997372
990736484
880109009
475421073
687770893
945004831
829776518
654324494
649078785
618853934
19...

result:

wrong answer 1st numbers differ - expected: '999908753', found: '148765427'

Test #8:

score: 0
Wrong Answer
time: 367ms
memory: 156960kb

input:

1000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

0

result:

wrong answer 1st numbers differ - expected: '3826404725', found: '0'

Test #9:

score: 0
Wrong Answer
time: 395ms
memory: 161776kb

input:

1000000
465660691 982007525 816592310 377030959 572981469 679249520 86377999 709561525 940473306 35102782 886143915 792819787 903287397 264564177 857982095 91486434 217197704 123118964 383387342 820268798 497623987 255010796 607884194 848568529 38169627 197987657 421323589 664004905 485409127 696844...

output:

374062433

result:

wrong answer 1st numbers differ - expected: '96094116015', found: '374062433'

Test #10:

score: 0
Wrong Answer
time: 380ms
memory: 164696kb

input:

1000000
665830082 788228483 245541444 289601309 641764988 150723484 925214020 557415731 310210969 379707835 517820381 883917428 134445288 775557009 444476671 89856268 655841087 888410254 37788122 694551869 563331754 488108584 839551943 415095075 445425438 35452604 562044723 640544531 146258096 66852...

output:

304268721

result:

wrong answer 1st numbers differ - expected: '431856043', found: '304268721'