QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #75609 | #4918. 染色 | 4182_543_731 | 100 ✓ | 2515ms | 462396kb | C++ | 4.5kb | 2023-02-05 21:42:08 | 2023-02-05 21:42:10 |
Judging History
answer
#include<cstdio>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
#define N 300500
#define M 22142500
#define ul unsigned long long
int n,q,s[N][4],mn[N];
ul vi[N];
struct sth{int l,r,v,d;};
vector<sth> si[N];
set<pair<int,int> > s1[N];
void init_s1()
{
for(int i=1;i<=q;i++)if(s[i][0]<3)
{
int l=s[i][1],r=s[i][2],v=s[i][3];
while(1)
{
set<pair<int,int> >::iterator it=s1[v].lower_bound(make_pair(l,0));
if(it!=s1[v].begin())
{
it--;
if((*it).second>=l)
{
pair<int,int> ri=*it;
s1[v].erase(ri);s1[v].insert(make_pair(ri.first,l-1));
si[i].push_back((sth){l,min(ri.second,r),v,-1});
if(ri.second>r)s1[v].insert(make_pair(r+1,ri.second));
continue;
}
it++;
}
if(it==s1[v].end())break;
pair<int,int> ri=*it;
if(ri.first>r)break;
si[i].push_back((sth){ri.first,min(ri.second,r),v,-1});
s1[v].erase(ri);
if(ri.second>r)s1[v].insert(make_pair(r+1,ri.second));
}
if(s[i][0]==1)s1[v].insert(make_pair(l,r)),si[i].push_back((sth){l,r,v,1});
}
}
struct BIT{
ul tr[N];
void add(int x,ul v){for(int i=x;i<=3e5;i+=i&-i)tr[i]+=v;}
ul query(int x){ul as=0;for(int i=x;i;i-=i&-i)as+=tr[i];return as;}
}tx,t1;
void solve(int l,int r,vector<int> ri)
{
if(l>r||ri.empty())return;
int mid=(l+r)>>1;
vector<int> s1,s2;
for(int i=0;i<ri.size();i++)
{
int id=ri[i];
if(s[id][0]<3)
{
if(s[id][3]<=mid)
for(int j=0;j<si[id].size();j++)
{
int lb=si[id][j].l,rb=si[id][j].r,vi=si[id][j].d;
tx.add(lb,vi);tx.add(rb,-vi);
t1.add(lb,vi*(1-lb));t1.add(rb,vi*rb);
}
if(s[id][3]<mid)s1.push_back(id);
if(s[id][3]>mid)s2.push_back(id);
}
else
{
int lb=s[id][1],rb=s[id][2];
ul ci=rb*tx.query(rb)+t1.query(rb)-(lb-1)*tx.query(lb-1)-t1.query(lb-1);
if(ci==1ll*(mid-l+1)*(rb-lb+1))
mn[id]=mid,s2.push_back(id);
else s1.push_back(id);
}
}
for(int i=0;i<ri.size();i++)
{
int id=ri[i];
if(s[id][0]<3&&s[id][3]<=mid)
for(int j=0;j<si[id].size();j++)
{
int lb=si[id][j].l,rb=si[id][j].r,vi=si[id][j].d;
tx.add(lb,-vi);tx.add(rb,vi);
t1.add(lb,vi*(lb-1));t1.add(rb,-vi*rb);
}
}
solve(l,mid-1,s1);
solve(mid+1,r,s2);
}
int ct,ch[M][2],lz[M],ci[M],sz[M],is[M];
ul fi[M];
void doit(int x,int s){if(s)lz[x]=s,ci[x]=s==1?sz[x]:0;}
void modify(int x,int l,int r,int l1,int r1,int s)
{
if(l1>r||r1<l)return;
if(l1<=l&&r1>=r){doit(x,s);return;}
if(!ch[x][0])ch[x][0]=++ct,sz[ct]=(sz[x]+1)/2;
if(!ch[x][1])ch[x][1]=++ct,sz[ct]=sz[x]/2;
doit(ch[x][0],lz[x]);doit(ch[x][1],lz[x]);lz[x]=0;
int mid=(l+r)>>1;
modify(ch[x][0],l,mid,l1,r1,s);
modify(ch[x][1],mid+1,r,l1,r1,s);
ci[x]=ci[ch[x][0]]+ci[ch[x][1]];
}
struct node{int l,r;ul su,lz;vector<int> li;}e[N*4];
void build(int x,int l,int r)
{
e[x].l=l;e[x].r=r;
if(l==r)return;
int mid=(l+r)>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
}
void pushup(int x){e[x].su=e[x<<1].su+e[x<<1|1].su;}
void doit1(int x,ul v){e[x].lz+=v;e[x].su+=v*(e[x].r-e[x].l+1);}
void doit2(int x,int y,ul v)
{
if(!v||ci[y]==0)return;
if(ci[y]==sz[y]){doit1(x,v);return;}
fi[y]+=v;e[x].su+=ci[y]*v;
if(fi[y]&&!is[y])is[y]=1,e[x].li.push_back(y);
}
void pushdown(int x)
{
if(e[x].lz)doit1(x<<1,e[x].lz),doit1(x<<1|1,e[x].lz),e[x].lz=0;
for(int i=0;i<e[x].li.size();i++)
{
int u=e[x].li[i];
doit2(x<<1,ch[u][0],fi[u]);
doit2(x<<1|1,ch[u][1],fi[u]);
fi[u]=is[u]=0;
}
e[x].li.clear();
}
void modify1(int x,int u,int l,int r,ul v)
{
if(l>e[x].r||r<e[x].l)return;
if(l<=e[x].l&&r>=e[x].r){doit2(x,u,v);return;}
pushdown(x);
modify1(x<<1,ch[u][0],l,r,v);modify1(x<<1|1,ch[u][1],l,r,v);
pushup(x);
}
ul query(int x,int l,int r)
{
if(l>e[x].r||r<e[x].l)return 0;
if(l<=e[x].l&&r>=e[x].r)return e[x].su;
pushdown(x);
return query(x<<1,l,r)+query(x<<1|1,l,r);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d%d",&s[i][0],&s[i][1],&s[i][2]);
if(s[i][0]<3)scanf("%d",&s[i][3]);
if(s[i][0]==3)scanf("%llu",&vi[i]);
}
init_s1();
vector<int> tp;
for(int i=1;i<=q;i++)if(s[i][0]<4)tp.push_back(i);
solve(1,150000,tp);
for(int i=1;i<=150001;i++)lz[i]=1,sz[i]=n,ci[i]=n;
ct=150001;
build(1,1,n);
for(int i=1;i<=q;i++)
if(s[i][0]<=2)
{
query(1,s[i][1],s[i][2]);
modify(s[i][3],1,n,s[i][1],s[i][2],s[i][0]==2?1:-1);
}
else if(s[i][0]==3)
{
query(1,s[i][1],s[i][2]);
modify(mn[i]+1,1,n,s[i][1],s[i][2],0);
modify1(1,mn[i]+1,s[i][1],s[i][2],vi[i]);
}
else printf("%llu\n",query(1,s[i][1],s[i][2]));
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 16ms
memory: 84296kb
input:
1000 1000 3 722 914 2141556875752121755 3 323 347 6433743606947304931 2 142 206 439 2 117 840 195 2 127 502 56 3 168 707 15142638115094015116 4 190 257 2 88 976 475 1 319 867 351 1 682 889 409 2 406 446 196 3 28 35 4899387534800369959 2 291 546 150 1 528 617 128 1 58 122 251 2 381 400 276 4 510 958 ...
output:
15128467772367689008 17361914246216994339 5483226026482017320 3033562207293358603 2081407883485577238 7431958406282818646 4664359672511637691 8517692808398202534 17884251128335023776 3389445997760709607 15161173652136060523 17246899135664170339 16659472119973467421 5618344994614112283 92650283427734...
result:
ok 288 tokens
Test #2:
score: 0
Accepted
time: 20ms
memory: 84272kb
input:
1000 1000 1 538 681 44 2 112 540 10 1 160 191 28 1 276 867 1 4 118 419 4 62 209 1 575 884 37 1 783 895 45 4 342 410 2 545 870 16 1 273 501 11 3 258 352 13270291835335737625 3 490 514 5208698592597571883 2 629 865 43 3 966 981 14431353048791951405 1 290 809 16 4 468 843 1 607 875 26 2 177 521 6 4 176...
output:
0 0 0 1090256298972435763 147836376791542005 2987455658418197192 17393388322162025577 0 15463425577465259729 5603739312727078592 9162759280430770517 5734982725161877299 17209386033616770563 4838930779004365643 849737692109005723 6426101344117061130 5419322161439603233 5062725202245147693 71096115354...
result:
ok 245 tokens
Test #3:
score: 0
Accepted
time: 22ms
memory: 84164kb
input:
1000 1000 3 99 666 17220025026447219412 4 5 483 3 749 845 16031212477837693538 3 133 609 17502764194597679430 1 20 226 5 4 251 561 4 633 824 4 200 311 4 519 771 1 441 468 4 1 143 922 2 3 125 229 12754000280540900298 1 498 505 6 1 363 450 3 2 271 554 3 1 114 704 4 2 120 814 2 3 690 982 45445988286128...
output:
7328512720450443476 7442164624875844502 14518824065043662144 15136137278022830944 9027578627713658176 14666047547670987011 9573739028108360400 15993305979184887208 14884581396130778517 17761136731703624839 13312122318790827838 14347674975080853967 17128890277609978434 9773479657321740818 15378095570...
result:
ok 256 tokens
Test #4:
score: 0
Accepted
time: 21ms
memory: 84076kb
input:
1000 1000 3 331 336 13313883338135403138 2 34 521 1 1 207 917 1 2 293 636 1 1 10 687 1 2 41 872 1 1 355 758 1 1 288 842 1 3 400 783 5775690383446019013 4 314 322 2 304 613 1 2 826 891 1 2 202 822 1 4 548 564 4 116 797 2 19 741 1 3 682 909 6383131735642614258 1 236 239 1 3 540 587 8352069600659472359...
output:
0 5953016150034565141 10352142132099319436 6096323733974212364 12116874695872864409 15347176369296045030 5941262347742323458 3620424356881155419 10127217571760838974 5461268237196718849 17374108689525300602 10962054618902200654 10589539750496832325 18040788904369214946 4431085881313941227 1086737541...
result:
ok 245 tokens
Test #5:
score: 0
Accepted
time: 24ms
memory: 86372kb
input:
1000 1000 4 508 569 3 464 647 9626512068323288850 1 261 912 260 4 11 44 4 277 438 4 284 694 2 58 226 212 1 457 503 39 2 706 712 21 4 284 619 1 512 792 423 2 157 161 53 4 277 536 1 366 980 414 1 316 876 190 3 371 886 9029081672906636708 4 194 444 2 745 753 461 3 213 319 890290010596372158 2 753 762 3...
output:
0 0 0 390789495368193264 7549612687959379704 1759106186637124642 4069257141547258216 0 17049456214560332466 12608950793396043246 15542879177249956503 5268553984485336740 3347535289204500833 1283339644428090794 900030301309717320 10617803241693535373 14165237887531480080 7981622196338660662 108862472...
result:
ok 249 tokens
Test #6:
score: 0
Accepted
time: 24ms
memory: 84304kb
input:
1000 1000 3 129 542 13655472611747991961 4 511 790 2 427 432 24 4 297 777 3 42 429 12538231273219784506 2 599 608 39 3 527 566 15984446643208694087 2 205 211 1 3 601 694 12523292657204424213 3 545 831 15344770091989840452 1 602 989 37 1 53 385 37 4 682 969 3 543 721 5478413773432004467 1 56 745 34 3...
output:
12700009880616055584 1938841074867628294 11101356538763217641 10137253135833169997 13873622059376146753 13337075822234643821 9115529121094266177 7669597812731439884 7653582597306726684 16408805096415770957 5310328737375184018 10833975347168974529 3499327095010911697 4157942280079245663 1226136409211...
result:
ok 237 tokens
Test #7:
score: 0
Accepted
time: 19ms
memory: 84164kb
input:
1000 1000 2 235 237 1 3 293 925 11446750964413798601 1 299 374 3 4 663 909 3 11 599 10235863487659693663 2 68 71 10 1 354 730 5 2 716 719 1 1 492 636 6 2 653 657 6 1 383 436 3 4 25 151 4 63 940 4 375 432 4 271 700 1 42 349 4 1 282 760 2 1 277 993 5 4 230 883 2 353 357 5 3 193 326 3721636915624045074...
output:
4995644932646857199 8682577773112482081 14198642487599396424 3213041208013041424 13539808857214091375 761700240778104149 303442926722239461 3516102455933096238 57413777171872180 7755609655116170430 4422876140281257386 5188821315335992835 12241893756112962715 16177149822898993950 340672744116294775 1...
result:
ok 262 tokens
Test #8:
score: 0
Accepted
time: 15ms
memory: 84276kb
input:
1000 1000 2 677 685 1 3 323 762 12895483491686386027 3 298 384 18175344572520049422 4 502 504 2 82 84 5 4 366 888 4 446 447 1 215 667 2 4 74 288 4 713 832 1 647 758 6 2 814 823 2 4 335 545 3 549 653 4845209895729503532 3 727 749 2017173238814894361 3 106 331 7491311112690514667 4 383 640 1 306 501 3...
output:
1792962327640054849 4602247259348913401 7344222909663220438 0 17584876078194546406 14152406924757806061 9115461223074385858 16394226226497421375 11880805806882569475 6738114177990764802 6873497294390714416 4519670768317052046 12682237596341027497 12763260220853210949 6314086074882193678 149826222253...
result:
ok 241 tokens
Test #9:
score: 0
Accepted
time: 20ms
memory: 84352kb
input:
1000 1000 1 34 37 5 3 126 206 14727478235725604056 3 654 744 18255408097680139947 1 480 887 3 2 949 957 12 2 73 73 4 2 475 479 13 2 629 633 60 2 855 863 17 4 693 699 2 841 848 16 4 99 497 2 591 593 11 4 475 475 3 662 665 9880886915713059518 2 759 767 7 3 138 500 17769308332561790789 2 377 385 1 1 63...
output:
17107392241503669933 12334116376362625112 0 6456951739835200564 9971073695561689148 2802027920063294567 1036164630077188382 17606737366739661456 3673719133547364878 14283911652166609210 10307419488382662895 7570930610113533112 4760136262978142135 2686644875969537451 16340864373011062989 166150323341...
result:
ok 238 tokens
Test #10:
score: 0
Accepted
time: 30ms
memory: 86396kb
input:
1000 1000 1 72 236 30 1 50 509 27 1 13 108 25 2 886 894 4 3 655 875 4803545865429381065 3 383 783 11671115136637467033 1 585 927 23 2 504 509 1 1 30 147 26 2 741 749 16 4 270 679 4 173 186 2 144 145 23 3 221 230 3690281936266615260 3 239 771 8308954142750294924 3 563 791 15967473094317050982 2 223 2...
output:
7741491917409221922 0 1184088091910697156 9402573550842177896 16347258322020142583 10075791157671528329 15790910225201268145 3569527660563963307 15857736879027467782 12504414326160398443 10919437795207910592 16960732844939675104 17997032562817801024 8392051279069707625 5000292839030073720 1114739402...
result:
ok 235 tokens
Subtask #2:
score: 15
Accepted
Test #11:
score: 15
Accepted
time: 1732ms
memory: 131520kb
input:
300000 300000 1 237576 237663 1 3 16150 16208 9270412155482010138 2 175648 175692 1 4 190836 190849 4 199010 199097 1 73976 298801 1 3 89902 89939 6418828085116455990 3 55415 55461 12238963685511262676 3 119825 119875 8146944792877919309 3 135103 135158 218634681842812119 3 127261 127352 13291431184...
output:
0 0 0 0 0 0 12272376591028786218 0 0 0 0 0 0 0 0 0 0 0 0 0 0 954290611784159519 0 3778617232493240005 8956067326602310519 7373452729428553855 16938285947326957203 0 0 14783754218831034862 7601682967357904165 0 0 0 0 0 0 11584905325916393312 0 0 4657169178464751085 17170356428308894805 0 0 0 0 148107...
result:
ok 74906 tokens
Test #12:
score: 0
Accepted
time: 1726ms
memory: 131452kb
input:
300000 300000 3 51867 51899 1302529772508711959 1 163791 163805 1 1 176666 176684 1 2 127516 127575 1 4 31898 31983 3 151469 151497 15873092426332082486 3 206515 206568 14236701547576343621 4 238241 238324 3 61219 262809 1734847965363776922 2 220344 220393 1 2 98688 148993 1 4 55989 56049 3 298350 2...
output:
0 0 0 10681306550146550313 6652613657187526474 11475494508458717824 811486215804201182 1622972431608402364 0 15901103964711581888 3357820396972179286 4094176851202742427 5379446566603537422 16250215233565986824 15431111627897858304 0 16250215233565986824 4917765691823749552 0 0 10297212258427286974 ...
result:
ok 74943 tokens
Test #13:
score: 0
Accepted
time: 1659ms
memory: 131456kb
input:
300000 300000 4 86816 86819 1 226565 246677 1 3 251963 251987 4817512795078102720 3 17122 202813 12262635941537918815 4 101129 101139 4 171789 171859 2 44072 166207 1 3 171011 171050 9516143677767859845 3 222046 222082 7458232785251868808 4 52499 166730 3 222551 222640 2035040917841558853 1 242195 2...
output:
0 5761786840950245653 3650180384843309913 13470892551030562504 16546298263213309450 3861341030454003487 15279334389549148006 5972947486560939227 0 11734734327511184880 0 10784511422263063797 16229557294797269089 3861341030454003487 10256609808236329862 15173754066743801219 0 1804317071900187272 5936...
result:
ok 74976 tokens
Test #14:
score: 0
Accepted
time: 1637ms
memory: 131624kb
input:
300000 300000 2 224303 224374 1 3 5249 5288 16547079035307299489 1 249405 249440 1 1 244932 244988 1 1 89040 89114 1 2 114166 114194 1 4 110077 110172 1 141920 141970 1 3 205203 205243 1118749945144490180 2 127281 127373 1 3 173359 173363 11110846146456890394 3 283255 283303 3242183420586937197 3 12...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2204476432060505976 0 0 0 0 0 0 0 0 0 6246016557504766932 3429185560983009296 0 0 0 0 0 0 0 0 8450492989565272908 0 0 0 244941825784500664 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10672427856181146758 0 0 14782553786312832860 0 0 0 2449418257845006640 0 0...
result:
ok 74803 tokens
Test #15:
score: 0
Accepted
time: 1592ms
memory: 131228kb
input:
300000 300000 1 220731 220734 1 3 219129 219133 1441661622928400529 4 297901 297906 3 226862 226869 2997910990656207321 2 154071 154073 1 1 239514 239523 1 2 264617 264626 1 1 66677 66680 1 2 108520 108527 1 2 493 498 1 3 93536 93536 1729223806369067100 1 99697 99702 1 1 98817 98817 1 2 268169 26817...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8523192685433180568 8523192685433180568 1420532114238863428 8523192685433180568 0 0 9943724799672043996 0 11364256913910907424 0 8523192685433180568 5682128456955453712 9943724799672043996 14205321142388634280 2841064228477726856 ...
result:
ok 74996 tokens
Test #16:
score: 0
Accepted
time: 1790ms
memory: 131200kb
input:
300000 300000 3 242005 245455 17402857150844839475 1 195499 202760 1 3 86348 87652 16350042050962992455 2 67513 70549 1 2 17581 20392 1 1 180566 187399 1 2 132424 136215 1 4 201 7568 4 29035 34787 4 159930 167082 4 117096 126668 3 115807 124052 6966836812432990399 4 24003 25402 3 16679 17045 1443793...
output:
0 0 0 0 0 0 0 0 0 0 1069304592552696348 0 0 0 0 0 18416266141863826215 0 0 0 3291332335248161760 0 355153960082695408 2339117343903337888 0 0 8313068146843994614 0 0 1842567308665326891 0 8807430591712594964 2810662510187183646 0 0 11269033645696727616 11110474990560302869 4659943295138724138 573269...
result:
ok 75196 tokens
Test #17:
score: 0
Accepted
time: 1784ms
memory: 131472kb
input:
300000 300000 2 129524 130230 1 3 97829 98681 14177044200280537874 1 117004 117036 1 3 75080 75625 7953158225766026866 3 222342 223044 592691174623108465 4 297810 298422 4 182525 182999 4 107197 107449 4 26126 26883 3 292284 292507 2229113056122186954 2 80055 80745 1 1 9570 10222 1 2 171443 171566 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6310142178115801295 0 0 0 0 0 0 0 0 0 14347829830854147244 0 0 0 0 0 0 0 0 3944750402169235976 0 0 14757788959901029185 1019326869378140182 0 0 0 0 10461260111479654801 0 0 16943243282109390662 0 0 0 7444098211629495683 16417881432838763511 10033696365246380464 15743721...
result:
ok 74887 tokens
Test #18:
score: 0
Accepted
time: 1880ms
memory: 131196kb
input:
300000 300000 3 60899 273136 17900506015963226324 2 255340 262254 1 1 47804 166274 1 2 228603 279002 1 1 229031 276929 1 4 136197 298489 3 162024 257244 7401373630232006099 1 215974 227652 1 3 119149 204343 7745371782660146547 1 152630 214299 1 3 96818 230022 73641545834168695 1 216242 238152 1 4 84...
output:
18154335184155868016 4395498840986882932 6677517497004993358 9589498140629496089 7527637927391730952 7561535112473928655 10721089906023321737 14674898849238760964 7537937300108454874 2088977973872526664 12681955574796639580 865433786514001673 6128943734780039177 6057697509332298715 66303342836821411...
result:
ok 74979 tokens
Test #19:
score: 0
Accepted
time: 1385ms
memory: 130088kb
input:
290000 290000 4 133423 133423 1 114519 114520 1 2 184800 184802 1 2 138774 138775 1 4 157293 157294 3 81666 81668 13806851267434892022 2 116280 116281 1 1 163245 163247 1 3 289833 289835 244401869236287882 3 135164 135164 8097051466237243604 1 113225 113226 1 4 43898 43900 4 289121 289121 2 133889 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 72459 tokens
Test #20:
score: 0
Accepted
time: 1507ms
memory: 129352kb
input:
290000 290000 4 130502 130504 2 15321 15322 1 3 275364 275364 4162744751939177223 4 99544 99545 4 100620 100621 3 193438 193439 13148803698890728003 2 125274 125275 1 2 241880 241882 1 3 168292 168292 2833035078327940594 3 27814 27816 10620786078931893277 4 136822 136823 3 56337 56338 74789752446323...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15159374354299362052 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 72567 tokens
Subtask #3:
score: 15
Accepted
Dependency #2:
100%
Accepted
Test #21:
score: 15
Accepted
time: 1841ms
memory: 152672kb
input:
300000 300000 3 19765 150566 5167493634543664094 2 118662 201848 4 4 127772 255639 1 363 249365 3 3 11598 175102 16530837351901358978 4 36444 234550 2 60767 191641 3 3 76143 190023 11283165360234648940 4 151255 257891 3 69394 97478 6131272952305682140 1 45277 77429 3 2 6151 122134 2 4 48165 93810 4 ...
output:
10556488787335954570 18212772968701168848 11437199959288606460 8399299997760384588 11718115706414345024 10430039748605185716 10791380095122215184 15944361710687625976 16135961443839657432 4434563019586156035 8749535087882211887 14176305221399051252 13418003553475512102 1702668605387454355 8261145120...
result:
ok 75134 tokens
Test #22:
score: 0
Accepted
time: 1871ms
memory: 152848kb
input:
300000 300000 4 162302 243671 4 108774 189675 4 39409 141166 3 4302 54955 2032314023908047574 2 112167 175614 2 1 64603 84223 1 1 21939 276073 4 3 89118 292192 16912914609874825743 1 42029 243136 5 1 6607 89923 5 4 84686 207749 2 90483 180706 5 4 90130 210937 2 3986 206420 1 4 160909 206368 4 231903...
output:
0 0 0 15873333503526926104 17121097540592268952 805172695466921900 6811875668698915906 2154704327756035887 13361063727983507916 9957465101949901033 2361020279627774791 9944802148218948334 8933006541057953482 8419054413218512287 7499374196247153755 2322814461374996893 5063455811544017944 181317836964...
result:
ok 75143 tokens
Test #23:
score: 0
Accepted
time: 1857ms
memory: 143372kb
input:
300000 300000 2 43881 209003 3 1 38394 210807 3 4 124088 246888 3 194292 294993 14965842988217960999 2 7268 260532 1 4 55356 258209 4 30614 125800 4 12228 217949 4 100914 139051 4 8626 289740 3 137200 197340 16581754139137487738 4 171679 297284 3 151002 169014 4048109911456650022 1 17955 191264 1 4 ...
output:
0 12391434633122534786 0 13554408553097148454 0 14226546569610905359 1258947742724700382 7975676018575701868 14699654335855404245 2836428098486907892 0 0 13075627585651397960 10137199037753101868 2560291716939532668 0 0 3965759468233765114 6675482547759797918 377136551797720692 8233780657308404454 5...
result:
ok 75299 tokens
Test #24:
score: 0
Accepted
time: 1777ms
memory: 136984kb
input:
300000 300000 2 38974 122425 1 2 154324 200509 1 1 105196 177261 1 4 22602 92336 3 116731 139521 3785691812380334046 1 50394 206585 2 1 43693 45939 1 1 150585 248398 2 4 58334 279236 2 29855 234629 2 1 134837 232356 2 1 33590 187995 1 4 45353 225094 4 5143 218406 3 132984 296259 13443883199001797437...
output:
0 4280063220620334354 4280063220620334354 4280063220620334354 12942102882948317922 0 515646398438274593 13960823896323729341 15121422257949422342 4050774890096600150 6827727476066314682 17032911577039160751 14980190398974067226 0 12348257822165863135 17797920071528495114 12049883758977904352 3741833...
result:
ok 74831 tokens
Test #25:
score: 0
Accepted
time: 1823ms
memory: 164160kb
input:
300000 300000 1 108325 170825 2 1 75180 198007 2 3 198502 269481 6155319409967550256 3 118439 204702 18208507226716555567 2 84689 109898 6 3 121350 125452 3240807257604350502 3 128113 279066 3858912386055261208 4 137324 156567 1 26763 296270 6 4 217992 250340 1 150551 168667 1 4 3954 44188 2 157016 ...
output:
2927707313254266164 7111691128492120360 0 0 7511433708585490232 12996595601304901602 10014652043142889389 7925859735776492962 2433266972111213673 2026742805035658622 16936296874308042384 15891253573118700198 16759433185048414435 13582699811806992711 9181279370616959841 10493668918954980833 170597511...
result:
ok 75346 tokens
Test #26:
score: 0
Accepted
time: 1883ms
memory: 163560kb
input:
300000 300000 1 142340 290896 4 2 106118 281594 1 1 125118 239219 1 1 146645 242467 6 2 94811 267059 2 3 196962 198060 3880842098740778491 3 177618 205437 7944189581324122015 3 21555 254873 6906922927176307854 2 176525 267586 5 2 5361 119139 8 4 154526 203127 2 18293 239801 4 3 1282 60367 1538377403...
output:
4193411294427687587 10423002897193835031 11930663020839708456 10934201185410919301 11258778839841246615 10115046511841330630 14827283835751603054 12316279356792582359 17344498406486238907 3494646827640168597 6786469609441453779 9547779074663416188 17436279776526979250 9418663493905667746 85616485436...
result:
ok 74957 tokens
Test #27:
score: 0
Accepted
time: 1858ms
memory: 166160kb
input:
300000 300000 2 77465 161500 9 3 25304 294829 14617411969686562512 4 481 38496 4 35950 178143 3 165700 208373 13782567429211730264 4 80676 219358 1 5209 156204 6 4 44953 267325 3 124226 186366 14440703711647784364 2 64226 237279 2 4 67503 78504 1 97863 224182 6 2 23945 44990 5 4 31956 286477 2 10843...
output:
5253569515166627152 2942368313631946912 1345383830117124384 18273134775908787008 2051655891689768736 3655662234790267468 3774822403807394432 14646651593312881196 9680623658269568240 17891947543856660464 6982652702368533886 2839122413995951781 9566827875742796835 11372470030965632244 3027091332166732...
result:
ok 74635 tokens
Test #28:
score: 0
Accepted
time: 1821ms
memory: 171096kb
input:
300000 300000 4 135648 234202 3 29647 165926 16840015053112602038 1 217908 299002 3 3 123595 288340 8410801434116764439 1 20871 74761 6 2 7028 15409 10 3 21503 98137 9149147557498946122 3 92468 149047 16265212067444614206 2 17774 292906 3 2 193818 239889 3 2 122417 296993 9 2 27240 260758 9 2 36377 ...
output:
0 4389850629296085054 8313708654800983154 10732548206643100566 3608783094651684135 9430655813522350698 9126304236188795410 10474480979708913992 3602960950417138945 4077117209803282681 5536612977701736005 606193025646921246 17033082339588459168 15145992704860749090 10957716210918004677 15173895978271...
result:
ok 74787 tokens
Test #29:
score: 0
Accepted
time: 1889ms
memory: 168568kb
input:
300000 300000 1 919 90143 7 1 102649 289927 4 4 93497 180570 4 110729 129647 4 6932 104274 1 57964 259150 3 2 212063 221156 3 4 2903 16160 1 75245 269199 1 3 8688 280846 4292968973522761247 2 8822 165545 9 3 14333 211258 3859369225063222502 3 115193 139733 1172430629984989898 1 50676 101214 5 4 1253...
output:
0 0 0 0 11664875968724206474 9533194866715364449 15519603103440872322 0 7060733740496120096 17469470569326166257 11894769427267838791 0 9827825259028825103 14146079548446117474 11424285263444710151 10412760283937555370 113877874699649381 2335183642059929974 15114038242525386820 6162699798640173037 7...
result:
ok 75181 tokens
Test #30:
score: 0
Accepted
time: 1643ms
memory: 170240kb
input:
300000 300000 3 45045 45112 8009006353435524131 2 282429 282443 8 4 99488 99511 2 41489 41565 9 1 250350 250386 8 2 55910 55924 2 3 139663 139696 11287649816917766743 4 55202 55266 3 202760 202846 12366404193921582437 3 153465 153480 9812145719085910030 3 167776 167817 17444421041035998999 1 87025 8...
output:
0 0 0 0 0 0 0 0 0 18186103062170250361 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11991416916054869196 0 14843646233087390032 0 6367304887820671070 14821396382473206458 5331491261753143882 0 0 0 10510559392090779822 3610188336539535216 16780515756041294950 1203396112179845072 9992652579057016228 0 0 16277682188744...
result:
ok 74910 tokens
Subtask #4:
score: 20
Accepted
Test #31:
score: 20
Accepted
time: 1584ms
memory: 196672kb
input:
300000 300000 1 85444 86076 59 1 41150 41411 71 1 278698 279414 45 1 238445 239202 56 1 29965 29984 49 1 282953 283272 37 1 34668 35653 86 2 198587 198744 28 1 270855 271611 58 1 2130 2965 773 1 161601 162298 937 1 50299 50435 36 1 100759 101198 64 1 120208 120543 84 1 295293 295732 34 1 112185 1129...
output:
0 0 16968625150574630951 16605993861994422737 14436884090003254733 0 3880767775473082445 6112413713545582398 0 17289176072916758003 0 0 0 10364128737969177934 0 0 995880312728861482 0 0 0 0 0 10433996744029883784 13368567004097850084 0 3861451384001627672 0 2134685396643390371 2335938625343203079 0 ...
result:
ok 100167 tokens
Test #32:
score: 0
Accepted
time: 1611ms
memory: 188752kb
input:
300000 300000 1 217891 287415 280 1 109091 109094 215 1 178397 178458 11 1 34114 34117 48 1 86577 86662 99 1 81392 81461 159 1 5842 5937 85 1 32285 32339 53 1 212941 212995 466 1 42038 42113 787 1 19627 19711 96 1 161983 266619 78 1 49816 222058 93 1 231964 231978 38 1 98426 98500 66 1 139172 139260...
output:
0 11692764325642035757 0 0 0 0 0 0 0 0 10626360660502640041 8974861558116311577 0 0 0 0 6828833927995630395 7675918871528237837 0 15346587511766135393 13255392782493978413 11587532788939849077 0 0 0 6764302870047383583 0 0 7400870183243479412 0 8589365144244158638 3886731025017654354 253988962743422...
result:
ok 100093 tokens
Test #33:
score: 0
Accepted
time: 1572ms
memory: 193396kb
input:
300000 300000 1 160271 160305 121 2 136868 136903 52 1 25761 183215 150 1 201646 201657 75 1 178637 178641 161 1 108624 108682 194 1 21955 90478 111 1 62044 62108 103 1 18137 18150 60 2 137444 137488 63 1 169356 169437 369 1 226170 226241 21 2 250536 250571 111 1 64083 64158 265 1 179107 179148 53 1...
output:
0 0 0 10146344313931218962 18059154134718308159 0 0 5482480617044727472 4903722043315669325 8795894026302189205 1504263091099301790 0 4566381908445435572 6966530244481722998 0 0 0 8601406932323617126 0 4231971134025119261 17835338178033113319 0 0 0 0 0 0 0 0 6727335030369532119 0 1158681340578803909...
result:
ok 99470 tokens
Test #34:
score: 0
Accepted
time: 2424ms
memory: 253752kb
input:
300000 300000 2 129741 129786 43 1 133731 133801 159 1 58344 83861 214 1 61033 61091 33 1 183553 183563 156 1 199271 199279 192 1 34576 34596 906 1 72891 80120 176 1 167427 167508 124 1 2964 3023 284 1 98570 98659 146 1 231952 232023 138 1 151151 151160 94 2 5131 5209 203 1 2869 2883 104 2 199205 19...
output:
0 0 4796201084925266965 0 0 0 13883685076285902517 0 0 9431529117273573445 4766573235145348929 1611897968597913432 0 0 0 2586063526252030814 0 0 16001876878405472178 17135272297629565994 0 17056443865906628232 0 4745294572652909898 8998783936939614344 7580363282108800106 0 16013946451858032933 0 477...
result:
ok 50062 tokens
Test #35:
score: 0
Accepted
time: 1114ms
memory: 164036kb
input:
300000 300000 2 85463 85536 76 1 1319 173260 147 1 217533 217619 256 1 10109 10176 289 1 55109 209902 262 1 81267 132527 169 1 23758 23766 393 2 271064 271083 283 1 78575 78665 257 1 198478 198506 327 1 130300 130393 669 1 86358 86366 198 1 13014 149678 56 1 39667 39738 27 2 61722 61803 172 2 12005 ...
output:
0 0 0 0 0 211139834562940132 0 0 0 0 9937788562274929249 9903884816325715188 0 0 2249898283594756228 4847122793324524440 13389982050708360868 0 0 0 17832939713973779542 10881562150273498962 17502970485710981903 8002363826031321384 7290681287509116914 0 4376837037219638409 3099055170068370790 0 18423...
result:
ok 125092 tokens
Test #36:
score: 0
Accepted
time: 902ms
memory: 269176kb
input:
300000 300000 1 1 600 1 1 1 598 2 1 1 596 3 1 1 594 4 1 1 592 5 1 1 590 6 1 1 588 7 1 1 586 8 1 1 584 9 1 1 582 10 1 1 580 11 1 1 578 12 1 1 576 13 1 1 574 14 1 1 572 15 1 1 570 16 1 1 568 17 1 1 566 18 1 1 564 19 1 1 562 20 1 1 560 21 1 1 558 22 1 1 556 23 1 1 554 24 1 1 552 25 1 1 550 26 1 1 548 2...
output:
0 0 0 0 0 0 2506763004086301860 17427921690879692440 0 0 0 0 0 0 0 0 0 0 0 0 12529173451446836357 0 0 8317424068741879477 0 0 0 15375344820100899566 0 0 0 0 0 0 0 0 0 0 0 6979511664378963244 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12078704023826942654 11918039685634475866 0 0 0 0...
result:
ok 75393 tokens
Test #37:
score: 0
Accepted
time: 940ms
memory: 261400kb
input:
300000 300000 1 1 600 1 1 1 598 2 1 1 596 3 1 1 594 4 1 1 592 5 1 1 590 6 1 1 588 7 1 1 586 8 1 1 584 9 1 1 582 10 1 1 580 11 1 1 578 12 1 1 576 13 1 1 574 14 1 1 572 15 1 1 570 16 1 1 568 17 1 1 566 18 1 1 564 19 1 1 562 20 1 1 560 21 1 1 558 22 1 1 556 23 1 1 554 24 1 1 552 25 1 1 550 26 1 1 548 2...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 5202743784850168886 0 0 4603927467884415342 0 4603927467884415342 9749533581125811360 2088840978649544692 0 18322607265021990624 0 0 9711321466745280504 4603927467884415342 2496249307634847047 0 0 0 0 0 0 0 0 0 0 0 0 5227856238668259348 47582809777024974 1200026012580389334...
result:
ok 75238 tokens
Test #38:
score: 0
Accepted
time: 816ms
memory: 446156kb
input:
300000 300000 1 1 300000 1 1 2 299999 2 1 3 299998 3 1 4 299997 4 1 5 299996 5 1 6 299995 6 1 7 299994 7 1 8 299993 8 1 9 299992 9 1 10 299991 10 1 11 299990 11 1 12 299989 12 1 13 299988 13 1 14 299987 14 1 15 299986 15 1 16 299985 16 1 17 299984 17 1 18 299983 18 1 19 299982 19 1 20 299981 20 1 21...
output:
0 0 0 0 10718922111423336564 10718922111423336564 0 0 0 10718922111423336564 10718922111423336564 0 0 9146817304949717077 13409051668444632193 2348108605912789755 0 0 9506780142003357434 0 0 9857982858752846941 13200643887683725279 0 0 0 0 7505599624584684325 0 5415306418116098549 0 1066421420982755...
result:
ok 75210 tokens
Test #39:
score: 0
Accepted
time: 955ms
memory: 149028kb
input:
300000 300000 1 1 1500 1 1 1 1500 2 1 1 1500 3 1 1 1500 4 1 1 1500 5 1 1 1500 6 1 1 1500 7 1 1 1500 8 1 1 1500 9 1 1 1500 10 1 1 1500 11 1 1 1500 12 1 1 1500 13 1 1 1500 14 1 1 1500 15 1 1 1500 16 1 1 1500 17 1 1 1500 18 1 1 1500 19 1 1 1500 20 1 1 1500 21 1 1 1500 22 1 1 1500 23 1 1 1500 24 1 1 150...
output:
0 0 0 0 8267058594554803676 0 0 0 0 0 0 9795094952976301450 0 0 0 0 0 0 9478972841234857817 0 2336196861175781959 0 0 0 0 0 0 0 0 7132376017696382137 0 0 3089475321960576786 7596711484866781532 0 13604716112274572028 15610753335934999776 832524808219417262 0 0 0 0 0 0 0 0 0 0 0 4306695857416496340 1...
result:
ok 91846 tokens
Test #40:
score: 0
Accepted
time: 1081ms
memory: 151796kb
input:
300000 300000 1 1 1500 1 1 1 1500 2 1 1 1500 3 1 1 1500 4 1 1 1500 5 1 1 1500 6 1 1 1500 7 1 1 1500 8 1 1 1500 9 1 1 1500 10 1 1 1500 11 1 1 1500 12 1 1 1500 13 1 1 1500 14 1 1 1500 15 1 1 1500 16 1 1 1500 17 1 1 1500 18 1 1 1500 19 1 1 1500 20 1 1 1500 21 1 1 1500 22 1 1 1500 23 1 1 1500 24 1 1 150...
output:
0 0 0 0 0 0 0 9251420100719027419 0 10437522002891643988 4472746676660461079 9253100888169842044 0 0 0 0 0 0 0 8566814495386720956 607008573332703067 0 14745303428233523745 0 6374585044919482064 0 10054674375899920618 1944753074502624222 2146697673259820164 0 0 0 0 0 0 0 0 0 0 0 0 0 1422096915848735...
result:
ok 90955 tokens
Subtask #5:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #41:
score: 10
Accepted
time: 169ms
memory: 108616kb
input:
40000 40000 4 576 27541 4 6386 23009 1 20941 21376 751 3 823 32062 5063552653037376179 2 13664 17318 2188 1 8143 18546 1303 1 96 22011 1709 2 20800 37184 3499 3 4098 33457 11559569033571630334 1 6686 15115 2973 3 11874 14936 5095502711361186497 4 423 21401 2 465 17984 1744 4 7029 8301 2 11477 13949 ...
output:
0 0 7508658702764009280 2818454508409587497 2691107458561732357 17091421403689417235 9257718243204186348 18298839084850992832 9718728949608108619 5190614606731169920 11954304750104910248 12646121248210666802 2227312579256095589 5111502619119685428 8250430884890452739 11243131780320731985 87960905481...
result:
ok 9994 tokens
Test #42:
score: 0
Accepted
time: 191ms
memory: 103856kb
input:
40000 40000 1 12559 31989 61 1 20540 26683 347 4 15157 37487 2 24282 26322 218 4 1359 27833 1 7254 26602 390 3 16275 21139 12479977116032246002 2 4908 14465 260 4 10322 31118 2 27812 36345 251 3 6605 36867 10550355865825144008 2 21869 33556 272 3 19324 25596 14673005058658741367 4 26342 37679 2 4961...
output:
0 0 6853922918742431474 3646519943965099888 0 6153542968187879966 11317375100468203353 14515564247017430579 1123692613983035864 8421461716963747926 11057180766482084640 7218499438058262744 16632423748903682936 12981519703119539378 6455100585298815773 10741834170238260825 5895587406382276070 15215727...
result:
ok 9998 tokens
Test #43:
score: 0
Accepted
time: 230ms
memory: 100672kb
input:
40000 40000 2 15566 23785 24 2 12710 16468 18 4 5516 17371 3 3315 13349 7262961801150345883 2 23729 28747 38 1 19232 20818 38 3 3184 29692 6742888815080704074 2 1038 35347 3 4 6222 21809 2 25565 32392 28 4 20233 28074 3 5505 28608 498741494423111384 4 18933 28203 3 9381 25723 3440819704761066563 2 9...
output:
0 7430965251653617072 9365572611306416852 9452915180814780494 9828429702921857547 1361176011493271989 1729610548391387594 14077746933625889736 9612912187363378426 4876178820848591192 8912775969232657188 4946375979248381299 10270284542887762916 1411726852422798281 13198455833731137318 167691818445823...
result:
ok 9912 tokens
Test #44:
score: 0
Accepted
time: 216ms
memory: 94036kb
input:
40000 40000 2 9034 14689 1 3 8078 24172 8446709360089751396 3 7183 29835 7453599722051325507 2 4573 18526 2 4 8131 20203 1 1835 5435 3 2 441 20550 1 3 10778 11992 15447703003373543258 3 34495 38063 7736539006391584864 1 27013 33214 1 1 31418 39483 3 4 6490 30518 3 4559 14183 8268753706355827434 1 19...
output:
7612717667627333823 9249750506545142521 6100689784483420778 7872964543753522561 10596753144290849576 6524294888743473164 5451252449228919069 1671137835218146742 750871853453121392 1489349358980656271 6411500492244724711 7109023910524010008 3116435585276723594 18174414762878528751 1113833908168544517...
result:
ok 9861 tokens
Test #45:
score: 0
Accepted
time: 178ms
memory: 107088kb
input:
40000 40000 4 5433 33171 1 9663 38939 903 3 17151 29086 489556798503134186 2 10552 19820 952 1 19329 21822 874 1 15050 29032 223 2 37346 37649 382 3 26321 30249 2479963200102780080 3 14760 29095 2734026925045709062 4 5466 16385 3 9918 38931 8415121231042101457 4 2006 24200 2 38060 38436 752 1 21540 ...
output:
0 18309202434030546972 979686583183183141 2581851821132002166 5012958776786493480 10933665070973329751 12628080033337595711 16419178355538396576 2762518489325336584 13222782748535709204 5727761150946371587 15050738623273638149 17299474625819832890 569931967967839962 9017407647608319798 7316951328699...
result:
ok 10112 tokens
Test #46:
score: 0
Accepted
time: 226ms
memory: 108040kb
input:
40000 40000 2 950 986 62 3 32665 39557 1459666198176499450 2 19953 20079 171 2 28787 28987 86 3 11890 13897 16992718997024881808 1 3626 12455 35 1 15855 36529 82 3 37186 37746 18180156315005212010 1 23269 24232 173 3 11213 19340 4696759065587628154 2 16539 16569 6 2 2899 2946 193 3 2837 10250 210882...
output:
12105169892515142560 15207756103116793500 11794421259914104692 13624790301027565746 2400203354172286864 2215748873640112924 3763435318174730947 7786144716893832273 16146982307292051892 16441554516053604807 16837160515212060861 2259579344222890040 3526780904914528886 18412540983454612307 176933060505...
result:
ok 9895 tokens
Test #47:
score: 0
Accepted
time: 237ms
memory: 103976kb
input:
40000 40000 1 33597 37399 35 1 3189 27051 33 4 29128 38689 2 28881 39271 38 4 9591 27710 2 20345 20607 5 2 23204 23413 49 3 8600 26762 5526158724337323840 4 17431 36715 2 34446 34815 35 4 11515 28618 3 2653 15822 585282263655737645 4 10269 12535 3 11483 26777 15384244170535151132 4 1531 15046 2 8475...
output:
0 0 11463529497709308160 16588044063991682048 1131920424397122879 16623280973432444722 11288569081185668380 14376690261992998376 1668074368341702052 4930851060101298228 2614792112049014607 3188055330635773710 3966359955538733297 6887038592542686756 16159820012510501165 826341539701747429 24522897197...
result:
ok 10141 tokens
Test #48:
score: 0
Accepted
time: 226ms
memory: 108664kb
input:
40000 40000 1 29905 30890 545 2 39668 39958 99 4 185 13527 2 33659 33942 16 3 4791 15377 11955402225202520566 4 9288 32278 4 1806 21644 2 30958 31154 90 3 2382 38460 10600044282569287487 2 37139 37474 11 3 17151 36696 12894272050760805953 2 22931 23010 32 3 29739 36518 12763324057917049064 4 10501 2...
output:
0 17547436625459570204 8732268497851594866 701026301823135620 8553236934023756096 4245457077681508586 10576542511136850929 5154480949819515280 4248351554003745886 17431300564677796727 6408823205966421392 12750657389420717791 17778617931738906058 16501130113232168445 17423220840960051353 106184677294...
result:
ok 9978 tokens
Test #49:
score: 0
Accepted
time: 214ms
memory: 107004kb
input:
40000 40000 4 27604 28631 2 29604 29755 14 1 1830 5370 65 1 401 27287 58 3 5772 19934 13988694129479509635 2 9867 10072 17 4 11589 39134 2 30627 30829 215 3 3984 14864 11509346671263077852 4 11811 12053 4 20893 37685 4 1176 31815 1 12470 23301 35 4 22376 25583 1 14435 33534 23 2 31419 31698 67 1 141...
output:
0 197962128235236046 16364649887748967981 0 2099217777114791253 0 2099217777114791253 0 12956974070382981388 7214100392957863815 13334987327345628689 18247441059178680252 14396813329827753491 4322569680482396718 15316119303924343622 612784626391564599 14852243166231139861 18252465950331399367 121453...
result:
ok 10006 tokens
Test #50:
score: 0
Accepted
time: 292ms
memory: 107656kb
input:
40000 40000 1 7674 9525 54 4 20790 21195 3 21059 27963 18316296184271697385 1 17831 29347 60 1 3915 9437 15 4 30267 32075 4 15044 38364 4 15961 16118 2 6544 6686 11 4 39217 39809 2 20363 20543 3 2 37851 37984 107 2 28580 28649 20 3 13965 20183 3399078880845549133 3 13020 37625 6599984329518697549 4 ...
output:
0 0 3147783043384564129 0 0 11737479225750595960 10771737015888382607 1812860509076860957 17363621120467743822 15140604598233199023 160798351867088240 6503789490688208382 12140022672524724959 10440900038123779961 3882849543552289779 11674143129754260317 13450257701895116730 16013901748674175210 9534...
result:
ok 8010 tokens
Subtask #6:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #51:
score: 30
Accepted
time: 1653ms
memory: 246700kb
input:
300000 300000 3 129611 275010 14341351429467829760 4 127236 143603 2 18751 205125 1844 4 61270 80245 3 208206 249052 14193747344989420994 2 2093 295014 2084 1 81546 149356 940 2 179606 252379 2772 2 14383 256937 2663 4 89229 126579 3 100841 188670 6555135009104383934 4 40537 225365 1 38738 145857 30...
output:
14848518730839352832 0 0 15211305378657874532 16892842552896212482 6486197657665586431 15739833644945869896 9939011811774675390 2012677554284141064 11583722257937973386 1131080345594804066 10748605953113388430 14428375485767987940 10992018949142597225 2609455098202925507 15298978000179853579 1675637...
result:
ok 75157 tokens
Test #52:
score: 0
Accepted
time: 1907ms
memory: 222056kb
input:
300000 300000 2 125196 221911 382 1 51170 155391 93 3 163057 295547 4410565431096393560 1 25386 207050 134 3 182181 298015 16644538900220565505 1 122044 157719 280 2 198991 274214 152 2 172427 256204 41 3 111051 297033 17333316754541350318 2 52535 205043 228 1 191112 224249 175 3 8723 263588 1147371...
output:
13503512360650187992 13779432954581527170 9961879177762037361 13197561688449717834 10314345330432980139 5417436424503571389 2547823627138931972 14094292696444186307 1559419488592062159 13134177668965810147 9218986549705221664 6319583390736749022 10459052197770751891 2980389259870893329 1548128586631...
result:
ok 75619 tokens
Test #53:
score: 0
Accepted
time: 1882ms
memory: 196592kb
input:
300000 300000 3 226196 270402 2287329681210043163 3 45739 282609 16338231735131611586 1 229416 286665 2 2 89237 253577 15 1 5089 288536 36 2 98301 108874 21 1 247840 286639 16 3 163956 219353 8346556662293571103 2 220313 240739 7 4 69925 297893 2 218945 292366 2 1 166817 219287 37 4 43838 183521 2 7...
output:
15686420889690912809 319240452768991744 7820460340265231523 6471366931322297854 6007619776834013853 9000729253990103902 12875408727486677404 5604777225752704820 17838784297373856974 6546440348527522854 7608219039603080219 3614723463032605130 12009578209844026988 10178907866398314416 1583645244267218...
result:
ok 75181 tokens
Test #54:
score: 0
Accepted
time: 1974ms
memory: 251024kb
input:
300000 300000 3 24667 164241 8140089758993671361 2 7448 8463 496 2 289294 291657 689 2 162379 163986 194 4 158773 299265 3 71084 160139 16119120434684008070 3 147592 239651 17635894136055333219 3 35390 138300 7822799401395259692 1 134209 184587 134 3 46108 83193 15308937210818042781 3 35138 237347 2...
output:
6157442075240623901 2420392845846149742 16608681081004029824 171373620995334910 8916070919264240728 1630912095930678758 15058247536172641986 17969658327532306789 10547670295210303552 1909452101020871225 8182880904604462515 12764799399792521773 4143165622492016077 7865137146411924260 5538375022769376...
result:
ok 75017 tokens
Test #55:
score: 0
Accepted
time: 1837ms
memory: 256184kb
input:
300000 300000 1 81890 112348 120 1 56298 254290 504 4 31196 256582 4 148270 256535 1 220606 275081 1763 4 64195 299613 2 180234 180390 363 3 42933 212178 14600869814812139820 2 59920 62564 2328 4 8841 37192 3 99136 173629 4667566885026199396 2 134436 137141 2100 1 149327 216450 810 4 13778 20646 1 2...
output:
0 0 0 0 0 16408166290300799404 629987134502751208 17499611391637086236 10330910451630410443 7671986046286391828 10899370631309403317 4039050183035784004 11906539668468489274 1552119370644313302 5486998537125801643 12076529817550091528 6496937940649187769 9055315833012539707 14700299658088683520 4881...
result:
ok 74823 tokens
Test #56:
score: 0
Accepted
time: 2035ms
memory: 246312kb
input:
300000 300000 4 182591 243353 1 84306 299592 224 4 239511 259350 3 67869 116437 6035107230182880481 3 11130 186457 13909329574605268337 1 71765 227338 126 3 181784 211627 5645376588146568789 3 209063 273981 11692548991175865951 2 21137 23055 112 1 126103 251071 144 3 219558 294891 150666192984797189...
output:
0 0 3980712652499161830 9050420235355229694 13264686689396884645 0 10249352494231059069 13459416985338085316 8125688644862358374 17626631330040118988 12081208742473473766 17193728623923101227 9165783539173247849 7429966195772439692 13002436411163980865 2179994942596364240 6322818338839638672 1022714...
result:
ok 74961 tokens
Test #57:
score: 0
Accepted
time: 2375ms
memory: 286972kb
input:
300000 300000 1 83754 213508 221 1 10638 21714 192 3 31502 33497 1769329837798204124 3 53614 130064 12394841571247145989 3 40813 42547 18196618713267432808 3 70189 294584 17576518265468576953 4 233279 234512 3 169429 264740 630330999517702145 1 243435 280130 52 1 40639 250817 411 1 45611 129430 206 ...
output:
14499252979500811202 3552459422229938111 13233327711524211412 16624900554222397127 11947342902244226086 12037224622744176429 14366974783801646087 6562521211834837544 1331421463755141920 13216251761038213073 41073780183763399 5193346301562674993 14274039798074788557 8908355504243741789 94512260277607...
result:
ok 60087 tokens
Test #58:
score: 0
Accepted
time: 2457ms
memory: 283028kb
input:
300000 300000 1 17786 61422 64 4 130421 214445 2 128000 129112 231 1 107914 276217 120 3 14026 25513 17647306113950260594 1 65412 231455 226 4 198109 222064 3 20320 139647 14636914588356486202 2 287571 289994 95 1 168497 200267 276 1 45007 224444 201 1 11379 283427 142 1 37894 77409 85 2 145658 1485...
output:
0 0 4791179129042500101 2111197755057396289 3097301653437636491 2592964163452272632 5662828126329081712 15262433432947354344 1006906708678843504 3755218307145203291 3382900142500912135 5640303050347933547 8395943385049901158 15747949400828468023 10262427463728684240 5224148839721892184 5137664808285...
result:
ok 60274 tokens
Test #59:
score: 0
Accepted
time: 2467ms
memory: 282792kb
input:
300000 300000 1 129320 169609 361 2 67956 70674 333 1 119238 125931 165 2 54464 56923 318 3 148134 214138 18330429125747412142 2 12707 15119 75 1 11867 100574 119 1 109774 263183 367 1 62481 253882 30 2 38992 39424 273 3 74566 241431 8693581929656401690 4 58030 59712 2 21589 22554 35 1 28598 54948 1...
output:
0 14117087291716796740 1634068529639224616 12402996554078744229 8774937183725144875 2992971545039484121 16479190985136542585 8108493207482060563 12812158074211083453 12136283098079928339 0 0 1215137701701082252 0 8659755038874979887 1911935642576936376 9031340577607113584 11300422260897997549 169794...
result:
ok 59433 tokens
Test #60:
score: 0
Accepted
time: 2515ms
memory: 271872kb
input:
300000 300000 3 139422 178391 1250413038763284461 4 42237 45234 4 256304 295448 4 121142 231082 2 75550 78404 13 4 14510 104071 3 23569 131610 8475891087337422941 1 19053 163330 15 4 182889 210875 4 586 145130 3 9064 200583 4592105751873120276 3 96468 136538 1749540336401024368 4 6917 163805 2 24886...
output:
0 0 10745021938269627314 0 0 226888720573030891 10915523122509252394 13164009268035286787 14682712594391240295 6417896601893173136 0 6609073613308038483 17410066127661645022 12357656411198819508 11515672082468037544 2971791894054681113 6386339849446947520 6300314723595261294 12374300710109711156 920...
result:
ok 59840 tokens
Test #61:
score: 0
Accepted
time: 1480ms
memory: 462396kb
input:
300000 300000 1 133557 222282 4784 2 21534 282347 61257 1 115943 298165 86505 1 122925 262673 139751 1 7179 22313 12794 2 108305 127463 40110 2 123134 125141 40331 1 195050 195357 76636 2 82495 256809 29047 2 103389 158498 21617 1 66391 123040 144667 1 92042 249498 32646 1 49507 123443 12042 1 24173...
output:
result:
ok 0 tokens