QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#431346#5830. 树Doqe20 3853ms466952kbC++172.2kb2024-06-05 13:15:452024-06-05 13:15:46

Judging History

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

  • [2024-06-05 13:15:46]
  • 评测
  • 测评结果:20
  • 用时:3853ms
  • 内存:466952kb
  • [2024-06-05 13:15:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10,B=20;
int n,I,U;
struct node
{
	long long vl[N],u1[N],u2[N];
	int Z;
	pair<int,int>ask(int d,int k)
	{
		long long 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(v1,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 (k1.first+k2.second-k1.second)<<I;
}
int task[N],cnt;
namespace Z
{
	long long s[N],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()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;for(int i=1;i<=n;++i)cin>>v[i],w[i]=v[i]>>B<<B,v[i]-=w[i];
	for(int i=2,u;i<=n;++i)cin>>u,to[u].push_back(i);
	int q;cin>>q;for(int i=1,x,k;i<=q;++i)cin>>x>>k,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);mem(u1);mem(u2);V.Z=C.Z=0;
		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: 10
Accepted
time: 235ms
memory: 293352kb

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:

31727996563
558747809
12352523
864526657694
91729843882
585197158
1628586765
922104954
8179034002
55032862871
1832814618
1719999173
57622639685
2418952903
118234180921
87152233480
403506301009
1458062157
139639462122
708763390
974312741
22160481283
541384937
113212700648
755479297
465075002
51201629...

result:

ok 1999 numbers

Test #2:

score: 0
Wrong Answer
time: 449ms
memory: 303860kb

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:

2509771019
102808896745
528899856
125427731
1953894159
2464509509394
5029632765358
586671581
4005599498625
798898621
468901916
1620113250
25990778
1594379152
3308397716395
30633535926195
1721547881
1491500623
2600435021950
15294999606926
263989598
1350176621
1471646893657
727716410
2229803315911
184...

result:

wrong answer 7th numbers differ - expected: '5038222699950', found: '5029632765358'

Test #3:

score: 0
Wrong Answer
time: 3846ms
memory: 466868kb

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:

321931698309777
64076180967287
131475963986298
185708290776287
4831569569703
52442485472452
91008406920138
133403236406826
287533250779236
123037923030010
128451400519770
8692690376743
14008926716805
64975200009377
310167311458051
15588672923645
74990661615898
73548655856496
66747995106786
217209901...

result:

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

Test #4:

score: 0
Wrong Answer
time: 3853ms
memory: 466952kb

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:

1437301063221
97701935687145
338254608150585
233422483708954
7394486620004
271005425392515
20855998530604
90676394967655
2535173725689
66531491075244
211302396787347
84667147279398
17869036410282
131905566783333
1860377236584
46206545856461
83860688140716
256990903795639
240676941954949
118317755786...

result:

wrong answer 2nd numbers differ - expected: '97809309869545', found: '97701935687145'

Test #5:

score: 10
Accepted
time: 3116ms
memory: 379600kb

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:

2258826661
938786622
1803221827
20412967786
11943681449
2783437365
16665953904
2720451454
1859550937
476794111
986063591
1579646962
14494868585
38176990
781099105
527479272
2392930136
2519423502
1620138021
23553905552
5107065078
6903424087
1206547828
18830610755
49589751
499629803
4275328259
1379311...

result:

ok 1000000 numbers

Test #6:

score: 0
Wrong Answer
time: 3144ms
memory: 381068kb

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
2995278795
3976195251860
35349434858403
976251948
369701890
43760580
1510389651
3077329408
66276877192581
716198149
190685967
105099778140620
13814507295164
557364187
1084839575
3104092
276690929
98348303567919
467852673
33049527
425554649
22765091293062
97629236742537
426018723
...

result:

wrong answer 4th numbers differ - expected: '3980490219156', found: '3976195251860'

Test #7:

score: 0
Wrong Answer
time: 3176ms
memory: 384656kb

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:

999908753
401770479
206046497556178
193787840033382
56957852879797
107753654656389
1146711843
100686370733209
2910590132
4981801495
1079679207
2140524944
75514756
9401494416885
74195158323836
167205592
58299231279516
1085743066
51805560485225
416441404289115
99041352230221
990736484
4798942061
37262...

result:

wrong answer 3rd numbers differ - expected: '206278425790162', found: '206046497556178'

Test #8:

score: 0
Wrong Answer
time: 3317ms
memory: 386456kb

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:

3826404725
4857376598
25168931
28
2928122114
64321117
0
334067473
60992
1
3
1
1
1
1
0
672988753
1
0
-1219602181
8
0
0
3
0
320487913
1
0
0
0
0
423617904
687492110
0
301348
220115086
10
35419106
37297971
1
1
28561996
517977935
3
2643348428
0
1132906086
2
1
4
2849416091
6
1896599693
0
3161693739
-34880...

result:

wrong answer 5th numbers differ - expected: '7223089410', found: '2928122114'

Test #9:

score: 0
Wrong Answer
time: 3265ms
memory: 384508kb

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:

96094116015
8235402248539
82802829883295
34173811442431
275400654
1384234654
64716568
11760715493464
10105959502420
263845831954
15614899754632
528398853
1456723425
1214744688
12956003630415
23475037
28389004781759
245789356
109738951
48492078993061
81049054474097
102619945
17628903081689
1556076353...

result:

wrong answer 2nd numbers differ - expected: '8243992183131', found: '8235402248539'

Test #10:

score: 0
Wrong Answer
time: 3439ms
memory: 390964kb

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:

431856043
520373616
77476535549367
7073484117901
63109555912234
13784534090260
762015332
4980856968909
1184478776
594507511
2675566549865
25639098895414
306250439
62500137
74937421363988
786078000
31346063852568
4162775188
4980015965966
877965179
18586202178188
1013123764
8936863238553
5679279442771...

result:

wrong answer 3rd numbers differ - expected: '77562434895287', found: '77476535549367'