QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#431346 | #5830. 树 | Doqe | 20 | 3853ms | 466952kb | C++17 | 2.2kb | 2024-06-05 13:15:45 | 2024-06-05 13:15:46 |
Judging History
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'