QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #108883 | #5696. 时空旅行 | myee | 40 | 512ms | 81004kb | C++11 | 4.4kb | 2023-05-26 21:01:46 | 2023-05-26 21:04:20 |
Judging History
answer
// 那就是希望。
// 即便需要取模，也是光明。
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
T ans=1%mod;
while(index)
{
if(index&1)ans=ans*base%mod;
base=base*base%mod,index>>=1;
}
return ans;
}
// Heaven and Earth... My guiding star...
int LK[500005];llt LB[500005];std::vector<uint>V[1200005];
voi Merge(std::vector<uint>&A,std::vector<uint>&B,std::vector<uint>&Ans)
{
Ans.clear(),Ans.reserve(A.size()+B.size());
uint i=0,j=0;
while(i<A.size()||j<B.size())
{
uint l=(j==B.size()||(i<A.size()&&LK[A[i]]<LK[B[j]]))?A[i++]:B[j++];
while(Ans.size()>=2&&(LB[l]-LB[Ans[Ans.size()-2]])*(LK[Ans.back()]-LK[Ans[Ans.size()-2]])
<=(LB[Ans.back()]-LB[Ans[Ans.size()-2]])*(LK[l]-LK[Ans[Ans.size()-2]]))Ans.pop_back();
Ans.push_back(l);
}
}
uint From[500005],tp;
voi push(uint id){V[From[tp++]]={id};}
voi pop(){tp--;for(uint i=From[tp];V[i].size();i++)V[i].clear();}
voi build(uint p,uint d)
{
uint d0=d;while(V[From[p-1]+d].empty())d--,build(p-(1u<<d),d);
while(d<d0)Merge(V[From[p-(1u<<d)-1]+d],V[From[p-1]+d],V[From[p-1]+d+1]),d++;
}
llt find(llt x)
{
llt ans=1e18;
uint d=0,p=tp;
while(p)
{
while((lowbit(p)>>d)&&(V[From[p-1]+d].size()||p+(1u<<d)<=tp))d++;
while(!(lowbit(p)>>d)||(V[From[p-1]+d].empty()&&p+(1u<<d)>tp))d--;
build(p,d);
auto&S=V[From[p-1]+d];uint l=0,r=S.size()-1;
while(l<r){uint mid=(l+r)>>1;if(LK[S[mid]]*x+LB[S[mid]]<LK[S[mid+1]]*x+LB[S[mid+1]])r=mid;else l=mid+1;}
_min(ans,LK[S[l]]*x+LB[S[l]]),p-=1u<<d;
}
ans+=x*x;
return ans;
}
uint Op[500005],Id[500005];llt X[500005];uint P[500005];
std::vector<uint>Son[500005],Q[500005];uint Cnt[500005];
std::vector<std::pair<uint,std::pair<uint,uint> > >Insert;
voi dfs(uint p,uint f)
{
static uint Last[500005],tp;
if(!Op[p])Last[Id[p]]=tp;else if(Last[Id[p]]<tp)Insert.push_back({Id[p],{Last[Id[p]],tp}});
for(auto s:Son[p])dfs(s,p);
for(auto s:Q[p])P[s]=tp;
if(Op[p])Last[Id[p]]=++tp;else Insert.push_back({Id[p],{Last[Id[p]],++tp}});
}
voi solve(uint l,uint r,std::vector<std::pair<uint,std::pair<uint,uint> > >&Insert)
{
if(Cnt[l]==Cnt[r])return;
uint c=0;for(auto s:Insert)if(s.second.first<=l&&s.second.second>=r)push(s.first),c++;
if(l+1==r||Insert.empty())for(uint j=l;j<r;j++)for(auto q:Q[j])X[q]=find(X[q]);
else
{
uint mid=(l+r)>>1;
std::vector<std::pair<uint,std::pair<uint,uint> > >L,R;
for(auto s:Insert)if(s.second.first>l||s.second.second<r)
{
if(s.second.first<mid)L.push_back(s);
if(s.second.second>mid)R.push_back(s);
}
std::vector<std::pair<uint,std::pair<uint,uint> > >().swap(Insert);
solve(l,mid,L),solve(mid,r,R);
}
while(c--)pop();
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#endif
uint n,q;scanf("%u%u%lld",&n,&q,&LB[0]);
for(uint i=1;i<=n;i++){From[i]=From[i-1];uint j=lowbit(i);do From[i]++;while((j>>=1));}
for(uint i=1,f;i<n;i++)
{
scanf("%u%u%u",Op+i,&f,Id+i),Son[f].push_back(i);
if(!Op[i]){llt x,c;scanf("%lld%*d%*d%lld",&x,&c),LK[Id[i]]=-2*x,LB[Id[i]]=c+x*x;}
}
for(uint i=0;i<q;i++)scanf("%u%lld",P+i,X+i),Q[P[i]].push_back(i);
Insert.reserve(n),dfs(0,-1);
for(uint i=0;i<n;i++)Q[i].clear();
for(uint i=0;i<q;i++)Q[P[i]].push_back(i);
for(uint i=0;i<n;i++)Cnt[i+1]=Cnt[i]+Q[i].size();
solve(0,n,Insert);
for(uint i=0;i<q;i++)printf("%lld\n",X[i]);
return 0;
}
// 那就是希望。
// 即便需要取模，也是光明。
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 13ms
memory: 60500kb
input:
100 100 1000004499 0 0 1 71139 12101 26676 1000002621 0 1 2 -388974 29267 3476 1000003458 0 2 3 717215 32379 13949 1000002483 0 3 4 -102846 14876 26114 1000004602 0 4 5 -623116 28528 562 1000000064 0 5 6 322377 4595 24356 1000000158 0 6 7 18175 25622 15156 1000001174 0 7 8 -365353 10113 32371 100000...
output:
4241956644 238137836482 5396490615 1659824452 49755292257 159807611 149696295 4144630087 506817535 1171087128 1003882937 478788676 6146863707 4794071846 1106338763 1915248639 1097971007 764285371 2693984312 1208749203 4022364829 2251181984 1793043685 2286227224 1070359224 7916254354 624426476 777477...
result:
ok 100 numbers
Test #2:
score: 5
Accepted
time: 481ms
memory: 77320kb
input:
100000 100000 1000002978 0 0 1 347020 317 26353 1000001834 0 1 2 452248 20085 9869 1000000053 0 2 3 88459 19993 29155 1000004823 0 3 4 408702 5984 24103 1000003587 0 4 5 154047 3585 26940 1000000592 0 5 6 -502738 31814 22490 1000001346 0 6 7 290918 11997 18888 1000003876 0 7 8 -534624 10237 23803 10...
output:
329118324 51003573 324784662 1000001788 4995331 1000036024 130412734 1000004054 1000009737 1000006368 1000001711 84362543 176864615 409025186 1000003720 70942481 1000032818 86013872 124120706 1000003542 106479459 152523067 389751358 1000000760 1000006493 1005264307 404936319 46997913 1000003917 1000...
result:
ok 100000 numbers
Test #3:
score: 5
Accepted
time: 492ms
memory: 76572kb
input:
100000 100000 1000000878 0 0 1 -952170 9287 22191 1000003732 0 1 2 -274534 16036 12281 1000001125 0 2 3 -404210 11647 4046 1000001045 0 3 4 -871605 29181 18123 1000003271 0 4 5 611274 1020 24724 1000001800 0 5 6 -200646 5240 19761 1000003891 0 6 7 -414769 18480 24157 1000004621 0 7 8 51036 21570 33 ...
output:
98997808 205244946 1000003353 33849053 1000097495 1000000667 1000003130 58602325 68078473 1000028241 8778840 1000001932 270743544 143710992 1000004172 82039752 1000000635 157660411 324274338 204188473 19740049 145593422 749646962 97671818 1000006174 51342694 404651220 45205977 104304451 748200731 30...
result:
ok 100000 numbers
Test #4:
score: 5
Accepted
time: 482ms
memory: 78292kb
input:
100000 100000 1000000614 0 0 1 155661 12105 18662 1000002227 0 1 2 411835 32120 32651 1000001243 0 2 3 997709 1036 3270 1000002437 0 3 4 -171196 18434 11609 1000004001 0 4 5 126520 22747 10378 1000000213 0 5 6 88917 23026 26587 1000003502 0 6 7 -578524 32600 27031 1000003599 0 7 8 -230133 25256 1963...
output:
1000003975 15145903 1000000334 24735331 615326000 54324931 245171352 546226413 825653202 308952950 1000194490 133416762 1000002735 1000002128 1000005520 1000000855 1000001874 369503897 1000029930 1000001934 1000003178 82342643 1000003161 37331106 1000002615 1000294658 1000002849 1000011107 100002071...
result:
ok 100000 numbers
Test #5:
score: 5
Accepted
time: 481ms
memory: 79128kb
input:
100000 100000 1000000489 0 0 1 -700834 3972 9939 1000001167 0 1 2 -512710 13506 21571 1000002213 0 2 3 297678 330 17792 1000003926 0 3 4 -674450 2751 13776 1000001342 0 4 5 -236428 29299 30173 1000002441 0 5 6 987829 22388 4052 1000000745 0 6 7 -742860 32276 21950 1000000576 0 7 8 -605162 182 29539 ...
output:
47889958 27284557 837115895 47889958 1000003863 94659930 126628180 837115895 1000003863 27284557 837115895 45287043 1000003863 1000003863 27284557 1000003863 1000010120 201535068 123858753 1005113305 837115895 1000003863 1000003863 1000003863 101123987 1000003863 837115895 203744943 1000003863 10112...
result:
ok 100000 numbers
Test #6:
score: 5
Accepted
time: 481ms
memory: 81004kb
input:
100000 100000 1000003819 0 0 1 668497 9175 24793 1000004457 0 1 2 -29071 20738 7926 1000002958 0 2 3 -222928 18653 16790 1000000208 0 3 4 432545 10294 8304 1000004331 0 4 5 850693 4288 8537 1000000904 0 5 6 50586 25567 19849 1000002002 0 6 7 682803 28863 12731 1000001730 0 7 8 -713971 6221 26712 100...
output:
1000001610 1000001610 1000001610 81384128 1000001610 1000001610 1000001610 700472905 1000001610 1000001610 1000060507 1000001610 265444467 1000001610 1000001610 1000001610 1000001610 934248670 1000001610 1000001610 1000001610 265444467 1000001610 1000001610 1000001610 1000001610 1000001610 94175997 ...
result:
ok 100000 numbers
Test #7:
score: 5
Accepted
time: 498ms
memory: 77568kb
input:
100000 100000 1000000263 0 0 1 381961 17121 24677 1000000369 0 1 2 -882895 30991 32450 1000003465 0 2 3 -291669 1646 14473 1000000461 0 3 4 -513350 1319 29046 1000001855 0 4 5 651223 31111 4843 1000003264 0 5 6 -142415 2637 5802 1000001334 0 6 7 925939 13394 21616 1000002952 0 7 8 -81339 7284 4478 1...
output:
272546498 122876442 44038703 1000007450 57659961 1000003750 790404366 3366413 1000005903 337220378 1000003145 272785020 30733002 112682930 166795683 83406370 88558097 1000007621 1000006883 1000002117 93897981 62728719 1000008863 1000000242 437605322 1000002155 229026742 1000022704 1000001407 1000001...
result:
ok 100000 numbers
Test #8:
score: 5
Accepted
time: 512ms
memory: 79164kb
input:
100000 100000 1000004558 0 0 1 469550 6836 11332 1000004792 0 1 2 -435120 18633 4592 1000004068 0 2 3 -197345 25270 25090 1000003541 0 3 4 876062 10491 10863 1000002840 0 4 5 411305 12923 21154 1000001411 0 5 6 -693785 21021 22135 1000002888 0 6 7 -829958 16030 20937 1000004049 0 7 8 299768 13772 10...
output:
62848378 1000007279 3636525 1000703024 1000006248 1000002923 116636307 1000001495 258248643 1000002997 91461307 1000004527 173616675 1000000538 1000011435 1000000765 1000003500 1000001703 1000004264 1000014412 331415880 58470528 1000001422 67316851 1000046260 78023416 1000378931 499184892 1010612181...
result:
ok 100000 numbers
Test #9:
score: 0
Time Limit Exceeded
input:
500000 500000 1000003241 0 0 1 -408344 16417 24891 1000002566 0 1 2 905197 28804 21421 1000002394 0 2 3 983860 16964 6910 1000003907 0 3 4 273351 6904 6980 1000001705 0 4 5 470878 9785 22065 1000003117 0 5 6 -181349 28769 24313 1000003842 0 6 7 10103 11314 9887 1000002976 0 7 8 195837 8874 11138 100...
output:
125819441 1000000741 458817667 1000002923 19027330 1000000741 1000002923 1000001750 956470103 257947575 81343830 37352688 1000000741 419893179 1000000741 217716883 809013777 935641892 1000000741 74835556 455688009 1000000741 1000000741 1000001750 1000001750 1000000741 1000000741 809013777 1000002923...
result:
Test #10:
score: 0
Time Limit Exceeded
input:
500000 500000 1000003565 0 0 1 441249 8786 28661 1000002799 0 1 2 -339582 19178 15869 1000000401 0 2 3 -617710 15350 23495 1000000434 0 3 4 558152 16199 30210 1000000775 0 4 5 -753221 25210 10160 1000004836 0 5 6 748945 24605 21495 1000002258 0 6 7 192699 9902 1862 1000001090 0 7 8 558176 5333 25281...
output:
1000002388 1000001540 1000001540 1000001540 407404347 429398700 1000001602 1000001602 1000001540 828034801 1000002388 82708228 1000001602 1000001540 470149340 1000001540 1000001540 1000002388 279784312 1000001540 168391090 1000001602 1000001602 83372841 1000071291 82708228 1000001540 1000002388 1000...
result:
Test #11:
score: 0
Time Limit Exceeded
input:
500000 500000 1000000694 0 0 1 -197399 28743 22363 1000002386 0 1 2 674400 8539 32509 1000002275 0 2 3 -655397 20397 32236 1000001346 0 3 4 -437867 17510 19651 1000001799 0 4 5 638836 24628 32506 1000002623 0 5 6 216428 26717 26970 1000002140 0 6 7 443425 17874 31011 1000001838 0 7 8 -276149 3469 10...
output:
result:
Test #12:
score: 0
Time Limit Exceeded
input:
500000 500000 1000000911 0 0 1 703011 21219 25858 1000004146 0 1 2 -450509 23942 26500 1000004224 0 2 3 -904492 19568 13252 1000002473 0 3 4 386250 8179 9129 1000003587 0 4 5 388518 28583 13345 1000003544 0 5 6 -912741 27178 23384 1000002533 0 6 7 -830324 9 500 1000004822 0 7 8 145641 31437 16095 10...
output:
result:
Test #13:
score: 0
Time Limit Exceeded
input:
500000 500000 1000004104 0 0 1 -627834 5936 31727 1000002050 0 1 2 -376309 24185 18306 1000000792 0 2 3 -653653 21438 22329 1000004342 0 3 4 419718 31952 2773 1000003233 0 4 5 43232 490 18832 1000003290 0 5 6 -756714 32656 10493 1000004554 0 6 7 457687 23674 9186 1000000438 0 7 8 374416 27597 10491 ...
output:
result:
Test #14:
score: 0
Time Limit Exceeded
input:
500000 500000 1000002705 0 0 1 41321 24456 19015 1000002721 0 1 2 -560286 22994 15579 1000002361 0 2 3 -370045 1584 32651 1000001211 0 3 4 195011 15308 447 1000001056 0 4 5 -527463 876 13803 1000003444 0 5 6 -375278 1805 2362 1000001983 0 6 7 -287070 4893 4427 1000000517 0 7 8 312247 24234 26870 100...
output:
result:
Test #15:
score: 0
Time Limit Exceeded
input:
500000 500000 1000003130 0 0 1 677709 24173 22392 1000000624 0 1 2 -777031 18590 6784 1000003929 0 2 3 -86438 23762 22452 1000000312 0 3 4 3071 4006 31305 1000000703 0 4 5 -872749 8885 27064 1000000422 0 5 6 -219250 27939 8468 1000004004 0 6 7 -773652 28030 10726 1000001132 0 7 8 250079 6089 24320 1...
output:
result:
Test #16:
score: 0
Time Limit Exceeded
input:
500000 500000 1000004708 0 0 1 -691751 6559 2221 1000002439 0 1 2 -278251 14398 16841 1000000118 0 2 3 471695 15793 18487 1000004210 0 3 4 762306 25076 11973 1000004561 0 4 5 461587 15302 1112 1000004809 0 5 6 -618153 19942 605 1000001237 0 6 7 817942 14121 7058 1000001075 0 7 8 -263282 25692 22079 ...
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
500000 500000 1000001286 0 0 1 4326 9806 9297 1000002021 0 1 2 478704 21169 5142 1000001306 0 2 3 -937404 19976 5498 1000000341 0 3 4 -220283 8076 27537 1000000243 0 4 5 -204077 2254 30533 1000003252 0 5 6 -984288 32021 28422 1000003470 0 6 7 602175 30903 7473 1000003786 0 7 8 -809410 24628 8835 100...
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
500000 500000 1000001795 0 0 1 361324 2552 7408 1000000472 0 1 2 348988 30279 16996 1000001032 0 2 3 544966 31580 28698 1000000425 0 3 4 570122 28243 983 1000001834 0 4 5 851074 10398 23304 1000001453 0 5 6 -240461 9817 31784 1000004590 0 6 7 -263551 29737 27720 1000004769 0 7 8 600263 20798 6630 10...
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
500000 500000 1000002538 0 0 1 -465573 289 5627 1000003715 0 1 2 -588592 31641 5312 1000003118 0 2 3 -738800 13520 16158 1000000104 0 3 4 568747 17751 22949 1000001564 0 4 5 460981 29409 28639 1000000010 0 5 6 884205 32393 16313 1000001623 0 6 7 -284901 3613 7487 1000004596 0 7 8 -898881 20708 31024...
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
500000 500000 1000002484 0 0 1 -966219 3481 6107 1000004544 0 1 2 591638 31287 19822 1000003873 0 2 3 -107979 4526 178 1000002820 0 3 4 -216181 24714 20640 1000004516 0 4 5 948520 14768 9024 1000000544 0 5 6 -419429 6489 30939 1000003565 0 6 7 171666 8402 11662 1000000239 0 7 8 -532670 31008 17553 1...