QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276595 | #7610. Bus Lines | AllTheWayNorth# | RE | 4340ms | 318144kb | C++14 | 6.3kb | 2023-12-05 23:35:20 | 2023-12-05 23:35:21 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
struct edge
{
int v,nxt;
}e[2000005];
namespace qwq
{
int st[22][1000005],val[1000005],b[1000005],lg[1000005];
void build(int n)
{
lg[1]=0;
for(int i=2;i<=n;i++)
lg[i]=lg[i/2]+1;
// printf("build:n=%d\n",n);
for(int i=1;i<=n;i++)
{
st[0][i]=b[i];
// printf("%d ",b[i]);
}
// printf("\n");
for(int i=1;i<=20;i++)
for(int j=1;j<=n;j++)
if(val[st[i-1][j]]<=val[st[i-1][j+(1<<(i-1))]])
st[i][j]=st[i-1][j];
else st[i][j]=st[i-1][j+(1<<(i-1))];
}
int query(int l,int r)
{
int nw=lg[r-l+1];
if(val[st[nw][l]]<val[st[nw][r-(1<<nw)+1]])
return st[nw][l];
return st[nw][r-(1<<nw)+1];
}
}
int getans(int u,int v);
namespace SGT
{
int tans[10000005];
int sum[10000005][2],ls[10000005],rs[10000005],ct;
void pushup(int x)
{
if(!ls[x]||!rs[x])
{
sum[x][0]=sum[ls[x]+rs[x]][0];
sum[x][1]=sum[ls[x]+rs[x]][1];
tans[x]=tans[ls[x]+rs[x]];
return;
}
sum[x][0]=sum[ls[x]][0];
sum[x][1]=sum[rs[x]][1];
tans[x]=tans[ls[x]]+tans[rs[x]]+getans(sum[ls[x]][1],sum[rs[x]][0]);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
ls[x]=merge(ls[x],ls[y]);
rs[x]=merge(rs[x],rs[y]);
if(ls[x]||rs[x]) pushup(x);
return x;
}
int modify(int x,int l,int r,int qx,int v)
{
if(l>qx||r<qx) return x;
if(!x)
{
x=++ct;
sum[x][0]=sum[x][1]=ls[x]=rs[x]=tans[x]=0;
}
if(l==r)
{
sum[x][0]=sum[x][1]=v;
return x;
}
int mid=(l+r)/2;
ls[x]=modify(ls[x],l,mid,qx,v);
rs[x]=modify(rs[x],mid+1,r,qx,v);
pushup(x);
return x;
}
int F(int x)
{
return tans[x]+getans(sum[x][0],sum[x][1]);
}
}
int n,m,h[1000005],t,sz[1000005],rt,vis[1000005],d[1000005],g[1000005],cov[1000005];
int gg[22][1000005],nid[1000005],sum[1000005],dfn[1000005],cnt,udfn[1000005];
ll nans[1000005],sumnans[1000005],qans[1000005],srt[1000005];
void add(int u,int v)
{
e[++t].v=v;
e[t].nxt=h[u];
h[u]=t;
}
void dfs1(int u,int fa,int ssz)
{
sz[u]=1;
int mx=0;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v]) continue;
dfs1(v,u,ssz);
sz[u]+=sz[v];
mx=max(mx,sz[v]);
}
mx=max(mx,ssz-sz[u]);
if(mx*2<=ssz) rt=u;
}
int bt,fir[1000005],las[1000005];
int lca(int u,int v)
{
if(fir[u]>fir[v]) swap(u,v);
return qwq::query(fir[u],fir[v]);
}
void dfs2(int u,int fa,int dep)
{
qwq::val[u]=d[u]=dep;
qwq::b[++bt]=u;
fir[u]=bt;
g[u]=u;
cov[u]=sum[u]=srt[u]=0;
dfn[u]=++cnt;
udfn[cnt]=u;
sz[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v]) continue;
dfs2(v,u,dep+1);
qwq::b[++bt]=u;
sz[u]+=sz[v];
}
}
void dfs3(int u,int fa)
{
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v]) continue;
dfs3(v,u);
if(d[g[v]]<d[g[u]]) g[u]=g[v];
cov[u]|=cov[v];
}
}
void dfs4(int u,int fa)
{
if(cov[u]) nans[u]=0,nid[u]=u;
else nans[u]=nans[g[u]]+1,nid[u]=nid[g[u]];
sum[nid[u]]++;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v]) continue;
dfs4(v,u);
}
// printf("dfs4:u=%d,fa=%d,nans=%lld,nid=%d\n",u,fa,nans[u],nid[u]);
}
void dfs5(int u,int fa)
{
sumnans[u]=nans[u];
// printf("u=%d,sum=%d\n",u,sum[u]);
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v]) continue;
sum[v]+=sum[u];
dfs5(v,u);
sumnans[u]+=sumnans[v];
}
}
int getans(int u,int v)
{
return sum[u]+sum[v]-2*sum[lca(u,v)];
}
int tmp[1000005];
void dfs6(int u,int fa)
{
srt[u]=SGT::modify(srt[u],1,n,dfn[rt],rt);
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v]) continue;
dfs6(v,u);
srt[u]=SGT::merge(srt[u],srt[v]);
}
// printf("dfs6:u=%d,fa=%d,sum=%d,%d,tans=%d\n",u,fa,SGT::sum[srt[u]][0],SGT::sum[srt[u]][1]
// ,SGT::tans[srt[u]]);
tmp[u]=SGT::F(srt[u])/2;
//qans[u]-=SGT::F(srt[u]);
}
int col[1000005];
void dfz(int u,vector<pair<int,int> > p)
{
SGT::ct=0;
int len=p.size();
for(int i=0;i<len;i++)
if(p[i].first>p[i].second)
swap(p[i].first,p[i].second);
sort(p.begin(),p.end());
len=unique(p.begin(),p.end())-p.begin();
// printf("dfz:u=%d,len=%d----\n",u,len);
p.resize(len);
dfs1(u,0,0);
dfs1(u,0,sz[u]);
int nrt=rt;
bt=cnt=0;
dfs2(nrt,0,1);
qwq::build(bt);
len=p.size();
// printf("dfz:u=%d,nrt=%d----\n",u,nrt);
for(int i=0;i<len;i++)
{
int u=p[i].first,v=p[i].second,l=lca(u,v);
if(d[g[u]]>d[l]) g[u]=l;
if(d[g[v]]>d[l]) g[v]=l;
if(l==nrt) cov[u]=cov[v]=1;
}
dfs3(nrt,0);
dfs4(nrt,0);
dfs5(nrt,0);
// printf("dfz:u=%d----\n",u);
int nw=0;
vector<int> son;
qans[nrt]+=sumnans[nrt]+sz[nrt]-sum[nrt];
for(int i=h[nrt];i;i=e[i].nxt)
{
int v=e[i].v;
if(vis[v]) continue;
son.push_back(v);
for(int j=dfn[v];j<dfn[v]+sz[v];j++)
{
int x=udfn[j];
qans[x]+=(sumnans[nrt]-sumnans[v])-sum[nrt]+1ll*(sz[nrt]-sz[v])*(nans[x]+1);
if(nid[x]!=nrt)
qans[x]+=(sz[nrt]-sz[v]);
col[x]=nw;
// printf("v=%d,x=%d,qans=%lld\n",v,x,qans[x]);
}
nw++;
}
// printf("dfz:u=%d----\n",u);
vector<vector<pair<int,int> > > ps;
ps.resize(nw);
for(int i=0;i<len;i++)
{
int u=p[i].first,v=p[i].second,l=lca(u,v);
// printf("i=%d,u=%d,v=%d,l=%d,dfn=%d,%d\n",i,u,v,l,dfn[u],dfn[v]);
if(l==nrt)
{
srt[u]=SGT::modify(srt[u],1,n,dfn[v],v);
srt[v]=SGT::modify(srt[v],1,n,dfn[u],u);
}
if(l!=nrt)
ps[col[l]].push_back(p[i]);
else
{
if(u!=nrt) ps[col[u]].push_back(make_pair(u,son[col[u]]));
if(v!=nrt) ps[col[v]].push_back(make_pair(v,son[col[v]]));
}
}
dfs6(nrt,0);
for(int i=dfn[nrt]+1;i<dfn[nrt]+sz[nrt];i++)
{
int x=udfn[i];
if(nid[x]!=nrt)
qans[x]-=tmp[nid[x]];
}
//printf("dfz:u=%d----\n",u);
for(int i=dfn[nrt];i<dfn[nrt]+sz[nrt];i++)
{
int x=udfn[i];
// printf("x=%d,qans=%lld\n",x,qans[x]);
}
nw=0;
vis[nrt]=1;
for(int i=h[nrt];i;i=e[i].nxt)
{
int v=e[i].v;
if(vis[v]) continue;
dfz(v,ps[nw]);
nw++;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
vector<pair<int,int> > p;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
p.push_back(make_pair(u,v));
}
dfz(1,p);
for(int i=1;i<=n;i++)
printf("%lld ",qans[i]);
printf("\n");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 89800kb
input:
6 1 2 5 4 6 5 3 1 1 5 3 6 1 2 3 6 4
output:
6 9 9 10 7 7
result:
ok single line: '6 9 9 10 7 7 '
Test #2:
score: 0
Accepted
time: 0ms
memory: 91844kb
input:
2 1 2 1 1 2
output:
1 1
result:
ok single line: '1 1 '
Test #3:
score: 0
Accepted
time: 93ms
memory: 106896kb
input:
16384 9137 490 3442 7239 1621 6904 13769 10250 14672 12572 14906 9437 6163 12339 15244 12016 3022 8670 3211 9106 11966 14817 15798 15876 6423 7394 894 7695 13877 1983 16342 15158 13574 15932 15125 10722 6989 15683 10335 8801 12301 4246 6166 3893 9347 12073 7897 12195 6510 3101 4526 15385 7017 7001 4...
output:
34355 34048 34070 34152 33992 33977 34077 42219 34103 33976 34065 34170 34072 34061 34069 34177 34068 34129 33872 50478 34059 33921 34153 34049 34034 33820 34132 34116 34361 33728 50043 34138 33855 33873 34309 34319 34068 50753 34135 34256 34159 34034 34056 34361 34171 34316 34058 34125 34019 34182 ...
result:
ok single line: '34355 34048 34070 34152 33992 ... 34333 33814 33294 34266 34337 '
Test #4:
score: 0
Accepted
time: 605ms
memory: 165020kb
input:
65536 44501 44259 59772 51161 51582 2027 2699 8610 5021 57211 60597 10270 29222 11423 38503 3833 52021 47503 47160 15296 61201 13465 20807 17239 7705 20234 32708 25663 7800 42265 29410 44963 32173 38920 49438 61282 25922 4342 40171 9819 12256 3995 41600 39383 57051 60932 44275 8351 8356 8295 3557 64...
output:
140178 136111 137025 136494 136304 137262 136598 135563 136530 135406 199677 137437 140282 136109 140127 136827 137235 136000 140738 139961 140081 142677 136544 201610 136181 136393 137013 137354 136855 135440 127050 136828 136781 137439 136518 185910 137170 136902 140686 136703 136847 137483 136337...
result:
ok single line: '140178 136111 137025 136494 13...63 136343 136858 137469 137325 '
Test #5:
score: 0
Accepted
time: 1740ms
memory: 249884kb
input:
131071 28270 44685 69228 113487 10873 80967 30958 109340 53006 103488 49569 111875 65021 32861 83043 36671 73613 119374 22104 91373 31527 27737 19718 27803 90762 87148 4096 41649 79425 111516 111950 123500 94580 61416 30879 18640 71251 76344 61698 28557 104875 59268 130832 61334 110927 109064 114115...
output:
273557 262588 264936 265663 265875 266353 265834 265712 376149 272370 267699 267626 267023 265515 266009 265333 278296 265843 265760 268149 267395 265340 271825 358266 268835 264845 266112 265586 265886 266374 265323 265391 266080 265499 278600 267120 265190 266164 266010 265240 265690 265370 264312...
result:
ok single line: '273557 262588 264936 265663 26...42 266079 265822 265939 266211 '
Test #6:
score: 0
Accepted
time: 2797ms
memory: 249848kb
input:
131071 4458 33223 28971 26710 73930 35887 19953 56582 19448 128895 117093 55994 68752 16511 37373 128666 1236 73891 64724 74049 67901 130974 130547 112357 99689 77958 76785 17021 37348 91813 67628 67488 96598 83555 17348 74226 98935 43076 75325 83600 59427 80746 74874 122816 71615 76503 112584 12953...
output:
131070 131070 131070 131070 131070 131070 131071 131071 131071 131071 131070 131071 131070 131070 131071 131071 131070 131071 131071 131070 131070 131070 131070 131070 131071 131070 131070 131070 131070 131070 131070 131071 131070 131071 131070 131070 131070 131070 131070 131071 131070 131070 131071...
result:
ok single line: '131070 131070 131070 131070 13...70 131071 131070 131070 131071 '
Test #7:
score: 0
Accepted
time: 1654ms
memory: 261020kb
input:
131072 20415 30901 24973 116658 50309 77228 14138 108175 122283 105254 80524 41943 16756 109108 113505 71325 9649 106367 125747 68730 27704 18831 12993 123364 57489 129424 96113 82877 44188 4472 5704 86388 73653 70774 41742 33080 6701 59595 80297 22453 59925 75977 88478 91057 97666 26155 30080 55382...
output:
267346 265658 267019 267148 266495 270630 265327 266124 266100 265926 265909 266766 265785 266284 265064 266584 266146 266937 271485 265805 265480 266087 267189 264771 266288 266965 270451 265977 265706 265268 265845 267259 265723 266249 266047 266159 270563 266086 265976 265845 265431 265535 265930...
result:
ok single line: '267346 265658 267019 267148 26...80 270694 266015 266101 265704 '
Test #8:
score: 0
Accepted
time: 2810ms
memory: 251196kb
input:
131072 48550 41416 47329 96006 106074 122239 948 75631 112525 117270 3358 7210 30446 101867 16965 11336 78371 58088 21081 102637 76025 92177 102359 2073 11618 50130 79150 120277 30847 51845 72881 58212 125170 71210 1909 8660 120236 81594 127702 49237 32584 53272 5049 20955 31844 125464 119524 100808...
output:
131071 131072 131078 131071 131071 131072 131072 131072 131074 131071 131071 131071 131072 131071 131071 131072 131072 131072 131071 131115 131078 131072 131074 131071 131072 131074 131071 131071 131072 131072 131074 131074 131072 131072 131074 131072 131078 131072 131077 131074 131071 131072 131072...
result:
ok single line: '131071 131072 131078 131071 13...71 131074 131072 131072 131072 '
Test #9:
score: 0
Accepted
time: 1665ms
memory: 270796kb
input:
131073 113890 124822 124669 105393 128510 64051 106729 33462 46677 33217 73570 96913 47532 130531 8593 45487 31793 58221 49510 82943 60351 62272 42636 37378 105049 94689 124230 45945 13194 123517 107928 62129 7572 15657 84304 122943 19818 59980 104221 18821 66457 91449 5072 101241 61822 5975 74471 6...
output:
266326 266281 266163 265817 265563 266929 265938 266796 265751 265513 266249 269598 266832 267310 265225 266439 266351 265499 397338 269917 266647 266193 266663 266655 269976 266497 326968 266761 266261 266672 265613 266103 265821 265496 265891 266411 265820 266598 266583 266154 265794 265587 266472...
result:
ok single line: '266326 266281 266163 265817 26...69 266180 266343 268563 266527 '
Test #10:
score: 0
Accepted
time: 2853ms
memory: 257896kb
input:
131073 30694 94981 78010 61921 83010 76565 7176 94673 24081 63906 107002 35122 72499 90887 98339 109807 48362 125168 5335 63101 127350 85675 13421 77562 2375 93853 10090 23323 91852 109502 21899 90367 56580 125803 108402 88380 30465 25789 73326 29902 60781 28952 113429 111420 15039 5166 48046 85049 ...
output:
131072 131072 131073 131072 131072 131072 131072 131072 131072 131072 131072 131205 131072 131072 131072 131083 131073 131072 131083 131073 131072 131072 131072 131072 131073 131073 131072 131072 131072 131072 131072 131072 131072 131072 131072 131083 131073 131073 131072 131194 131205 131072 131072...
result:
ok single line: '131072 131072 131073 131072 13...72 131072 131072 131072 131072 '
Test #11:
score: 0
Accepted
time: 4329ms
memory: 304368kb
input:
200000 303 187602 17443 90857 141584 9689 98281 37564 34044 95754 47052 855 176062 121958 162738 96296 89316 164507 150496 42874 12673 1114 24877 131213 196802 28543 78558 84878 102156 146853 143846 158517 167159 69770 16743 9610 169056 115672 127506 149401 4110 24877 150803 72957 71484 24773 50738 ...
output:
200000 200000 200001 200009 200000 200000 200000 200004 200000 200001 200009 200040 200000 200000 200371 200001 200001 200000 200005 200000 200103 200000 200005 200001 200002 200000 200004 200000 200004 200002 200001 200004 200000 200004 200103 200000 200001 200001 200009 200004 200000 200000 200009...
result:
ok single line: '200000 200000 200001 200009 20...00 200000 200000 200001 200001 '
Test #12:
score: 0
Accepted
time: 4340ms
memory: 303704kb
input:
200000 91261 108952 134236 7809 30750 140934 69514 100626 174539 64746 143756 139270 75999 163614 73309 112948 110641 128653 77295 196144 112549 15212 29529 58568 34742 48981 160465 37279 60772 47631 116260 164168 140007 138837 152400 41600 46137 103771 122809 991 98335 53547 71446 60454 182926 9505...
output:
259717 224832 623118 233065 221904 225116 248347 347328 229609 227413 369557 318840 231176 228808 255754 223173 224794 339975 239690 230310 252630 225403 411260 227236 240962 241886 231002 333731 242413 226478 294844 238042 224724 260233 244253 330794 247474 231750 283982 269581 221874 223906 258662...
result:
ok single line: '259717 224832 623118 233065 22...21 228869 224599 227932 221883 '
Test #13:
score: 0
Accepted
time: 0ms
memory: 89764kb
input:
3 3 2 1 3 1 1 2
output:
2 2 2
result:
ok single line: '2 2 2 '
Test #14:
score: 0
Accepted
time: 4270ms
memory: 300356kb
input:
200000 139347 147721 117297 105382 77192 197023 48135 123968 192172 102714 134778 129103 89903 62952 133541 38908 157094 5072 98697 154745 126329 161358 10578 175752 174214 105555 128475 68598 37906 187226 161543 11243 153891 97890 8751 74708 1967 76185 67263 189209 68782 199622 163887 141633 176004...
output:
322099 242574 317560 692202 290760 228294 365767 338369 353452 316822 250525 392353 334147 230213 228522 235083 402948 230055 390730 404058 356419 260604 408966 344671 228306 285866 230909 242013 251050 312234 247399 300014 275307 396635 301629 245071 324672 317767 338521 318599 251342 394339 233005...
result:
ok single line: '322099 242574 317560 692202 29...72 316661 233236 238848 229144 '
Test #15:
score: 0
Accepted
time: 4126ms
memory: 294488kb
input:
200000 48091 145114 125125 28630 12239 122518 46999 28599 9536 79090 173383 59215 130797 80267 19356 192091 70170 63308 51543 84599 75128 23622 67565 61168 59080 1306 169051 40849 189030 31373 186212 42004 87480 32135 81468 163743 112945 69079 83894 23714 71122 15016 66755 85285 115054 110310 3811 4...
output:
352484 361697 353433 343102 240568 351386 298596 364831 245058 343138 260208 258681 345310 370366 432737 233034 361503 405572 231637 345073 347968 358736 232149 353892 398610 251240 431731 345221 343820 346239 347060 263522 231954 393526 360199 379830 373877 236327 353553 603138 426721 241772 231332...
result:
ok single line: '352484 361697 353433 343102 24...94 353707 382734 557096 397978 '
Test #16:
score: 0
Accepted
time: 4104ms
memory: 300536kb
input:
200000 100856 98512 7263 55794 118589 8600 181408 78844 136926 96808 184915 65090 34153 123222 81629 114888 41173 81343 115395 158775 74974 23534 3836 68657 105617 97663 76598 41608 28787 13900 100912 96168 68712 136985 80113 56372 112283 126282 119777 137629 165008 120438 53426 26030 78094 83600 18...
output:
385605 380500 397966 236324 577262 360773 233242 371405 362611 369437 365600 386222 381693 250148 585672 376752 366566 253349 377273 388253 269521 263111 427010 369947 392348 389317 423904 233334 252314 359670 387478 359580 233140 434587 321068 233635 234253 365444 235007 599141 373618 362626 360872...
result:
ok single line: '385605 380500 397966 236324 57...45 241541 407294 372787 439030 '
Test #17:
score: 0
Accepted
time: 3749ms
memory: 294404kb
input:
200000 180714 64749 50294 63588 118425 45210 19449 119242 106397 111631 165556 58767 54399 99326 53093 31192 63207 75350 36668 124604 80509 124402 69687 129300 190278 28893 50196 134511 46249 169905 58139 53110 87694 22713 75518 99566 179781 17413 110365 34464 27454 193678 130171 47991 174341 58040 ...
output:
409591 396787 395821 239526 599035 470672 428144 397055 392027 394551 439143 394596 388894 404545 405346 348418 392047 593706 389817 326075 394143 396508 393233 425007 399946 397646 399058 595850 413576 389700 412903 417007 392550 401326 462627 392588 275297 400751 395385 395593 398254 244287 415091...
result:
ok single line: '409591 396787 395821 239526 59...05 410665 400756 392347 468683 '
Test #18:
score: 0
Accepted
time: 3557ms
memory: 294944kb
input:
200000 30933 92193 77862 62042 158213 175855 16780 145844 1108 114460 160478 9352 82719 112145 142088 62191 15793 183238 129644 169759 70407 173026 113244 57481 56239 24998 45541 79142 119610 110586 99594 22588 198974 169804 99392 125472 63750 161647 119893 161584 25389 132271 48396 138568 63641 385...
output:
603675 406633 422392 407572 409097 406433 406205 407058 420803 408723 464911 425536 410465 481876 407605 576569 607865 431005 412229 419713 410499 412896 408749 606713 403730 427776 408406 407828 606627 417814 407449 407308 404474 470975 410304 412734 413266 406163 408984 403576 406249 405420 406787...
result:
ok single line: '603675 406633 422392 407572 40...37 412018 406965 408388 609396 '
Test #19:
score: 0
Accepted
time: 3177ms
memory: 310372kb
input:
200000 53058 81131 171867 48542 51107 57582 48378 14960 8723 5010 161623 59486 63739 114343 146033 97144 38395 143404 106830 120862 166654 142711 17747 75675 115326 57950 141271 125647 172839 194710 87377 142587 179489 111106 83353 29003 25273 100804 126366 129214 377 22864 136214 154742 26790 69245...
output:
410194 414485 812212 409671 417799 607529 444323 439505 398218 413075 406897 417525 409744 418032 416266 417491 409650 420260 411460 411034 412949 416088 409367 613828 410798 608605 411940 403730 303206 404280 403397 612430 415487 395351 408532 419160 418430 410453 416946 618525 408493 411347 423058...
result:
ok single line: '410194 414485 812212 409671 41...85 413258 416216 407728 410996 '
Test #20:
score: 0
Accepted
time: 2861ms
memory: 318144kb
input:
200000 59158 51892 164326 130454 199875 147324 154595 198150 175219 8364 108094 125630 131696 93091 63992 91024 129143 10985 79964 129833 193970 137750 130697 130080 103615 11370 83315 137120 141683 168619 130441 168268 163828 3410 76009 110247 59575 155246 124663 70547 152379 94187 114650 89902 282...
output:
418785 413603 418648 419139 412502 406320 410977 412124 407379 402640 419358 416320 407945 412692 414142 413490 413278 416746 410595 418751 415083 413390 420604 412779 418777 613129 408587 406350 413893 413360 413188 418726 401511 408363 419082 414357 526212 413422 601652 413018 411076 418011 413908...
result:
ok single line: '418785 413603 418648 419139 41...13 414570 417977 436541 415929 '
Test #21:
score: 0
Accepted
time: 2615ms
memory: 246804kb
input:
200000 118922 134567 199816 52066 84326 118291 140839 91527 41156 196216 193057 168156 5712 147301 151841 143708 95806 153816 135331 166094 167087 140971 112587 136986 97546 33542 171749 67249 173810 197325 61841 77212 116769 138505 62675 30261 101896 50402 91780 178503 28880 20528 87860 154449 8267...
output:
13168057510 11173781860 10146494712 16156520832 13448332006 10989071050 10508931040 10037228302 12324541582 10347691962 10028724240 12081412506 11563767480 10187676300 12443176612 10048783240 11774557750 16609608700 15055565506 14134682902 10028318362 11956514056 10158873420 15322067256 11664028056 ...
result:
ok single line: '13168057510 11173781860 101464...110756 18856409772 13401863950 '
Test #22:
score: 0
Accepted
time: 2501ms
memory: 238528kb
input:
200000 74212 14285 54279 26014 34653 159417 195912 97270 147173 32677 7753 76853 47200 73990 93075 63990 186243 107173 105569 133096 11068 124684 66637 118271 143298 65684 108858 167243 83551 3112 227 38450 120359 109554 42942 133316 29887 192012 143614 97487 95789 105585 33495 155927 63945 45781 13...
output:
9636839798 7803026188 5944133824 5022351612 5824014810 5466796520 5799132740 5020579868 5118628970 5167194124 5461475062 5089909366 9928608548 5018143302 8863291306 5172571016 6712586160 5054073146 6479682294 5284856118 6274156336 8690429520 8083401824 5218118942 5428913248 9540526484 5044191702 640...
result:
ok single line: '9636839798 7803026188 59441338...48485482 5237756436 7380188354 '
Test #23:
score: 0
Accepted
time: 2344ms
memory: 230864kb
input:
200000 92107 93965 159733 109184 192340 76154 84291 151200 22927 32573 60309 166432 136353 52220 46466 195262 169506 58576 155186 181682 129591 45964 5016 99216 173166 72054 186200 95903 105499 17449 196067 122431 177329 57447 66939 50332 67438 62704 184758 103097 13997 9543 159320 119688 67521 1795...
output:
2647717540 2669067610 2536317714 4564900018 4938957828 2523583466 2587289770 4089042968 2538144128 3083739956 2846104828 4939992978 3010058766 2640028282 3303357298 3059661060 3682213356 2518446598 4593066520 3175275992 3500605592 2512952006 2728454602 4496768570 3328605822 3999565194 3852256448 268...
result:
ok single line: '2647717540 2669067610 25363177...80561904 3193035228 3613793802 '
Test #24:
score: 0
Accepted
time: 0ms
memory: 91852kb
input:
3 2 1 2 3 2 1 2 2 3
output:
3 2 3
result:
ok single line: '3 2 3 '
Test #25:
score: 0
Accepted
time: 2004ms
memory: 224560kb
input:
200000 97274 52191 170698 12492 56055 38209 195479 171683 182171 104124 48099 163495 28208 143687 98769 194755 69808 115617 120295 101563 38553 94131 23270 112248 131587 158997 31823 162234 83013 181537 191160 172757 189345 102179 151357 192653 101899 101918 118524 182209 14724 52904 14881 114877 65...
output:
315521802 582270214 374296028 430835082 461750522 547580860 458554994 341017246 385629432 318527132 308318016 304520182 306364072 333253596 574032542 314446098 521022698 407699078 460444652 298495576 297416182 437728058 483072350 552191872 358261158 439148560 390171338 424559912 452883186 322464158 ...
result:
ok single line: '315521802 582270214 374296028 ... 501733906 435471700 498539190 '
Test #26:
score: 0
Accepted
time: 1874ms
memory: 230988kb
input:
200000 149275 37122 186803 180793 142343 25474 2212 104891 153840 36431 70840 95284 71111 176237 88737 94284 132867 69692 115881 67641 31109 97047 21627 157384 46886 161629 143575 184545 168978 54964 39205 42574 168223 32975 102385 50620 84750 126621 109786 165166 80248 112638 7161 54171 108145 1160...
output:
156800727 185140211 160861639 163079193 181736213 166433065 169894763 127848699 165191659 128374161 137184613 136296451 122378297 150527067 186298237 142165489 171740743 163923655 144726201 186139667 216535769 143134125 206500761 150034699 166563761 130542877 215959573 147380353 174762851 188816095 ...
result:
ok single line: '156800727 185140211 160861639 ... 198578685 168950583 138834499 '
Test #27:
score: 0
Accepted
time: 1371ms
memory: 227048kb
input:
131071 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 6 14 7 15 7 16 8 17 8 18 9 19 9 20 10 21 10 22 11 23 11 24 12 25 12 26 13 27 13 28 14 29 14 30 15 31 15 32 16 33 16 34 17 35 17 36 18 37 18 38 19 39 19 40 20 41 20 42 21 43 21 44 22 45 22 46 23 47 23 48 24 49 24 50 25 51 25 52 26 53 26 54 27 5...
output:
131070 131070 131070 182280 182358 182396 182254 212773 212880 212959 212834 212906 212874 212780 212908 231778 231899 231958 231796 231820 231879 231765 231895 231892 231897 231788 231917 231935 231630 231878 231824 243684 243863 243938 243663 243836 243843 243815 243694 243798 243698 243831 243802...
result:
ok single line: '131070 131070 131070 182280 18...10 262108 262110 262109 262109 '
Test #28:
score: -100
Runtime Error
input:
200000 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 6 14 7 15 7 16 8 17 8 18 9 19 9 20 10 21 10 22 11 23 11 24 12 25 12 26 13 27 13 28 14 29 14 30 15 31 15 32 16 33 16 34 17 35 17 36 18 37 18 38 19 39 19 40 20 41 20 42 21 43 21 44 22 45 22 46 23 47 23 48 24 49 24 50 25 51 25 52 26 53 26 54 27 5...