QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#768551 | #7767. 数据结构 | zhouhuanyi | 100 ✓ | 1993ms | 367660kb | C++14 | 6.3kb | 2024-11-21 12:11:18 | 2024-11-21 12:11:18 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cassert>
#define N 200000
using namespace std;
int read()
{
char c=0;
int sum=0,f=1;
while (c!='-'&&(c<'0'||c>'9')) c=getchar();
if (c=='-') c=getchar(),f=-1;
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum*f;
}
struct reads
{
int l,r;
};
reads operator + (reads a,reads b)
{
return (reads){min(a.l,b.l),max(a.r,b.r)};
}
int n,m,dfn[N+1],leng,depth[N+1],rev[N+1],rev2[N+1],sz[N+1],top[N+1],fa[N+1],hs[N+1],num[N+1],length;
__int128 ans;
bool used[N+1];
vector<int>E[N+1];
vector<int>ES[N+1];
vector<reads>dp[N+1][4];
vector<reads>DP[N+1][4];
vector<reads>DP2[N+1];
vector<reads>DWP[N+1];
bool cmp(int x,int y)
{
return num[x]<num[y];
}
vector<reads>operator + (vector<reads>a,vector<reads>b)
{
if (a.empty()) return b;
if (b.empty()) return a;
int ps=0,ps2=0;
reads d=(reads){0,-1};
vector<reads>sp;
while (ps<a.size()||ps2<b.size())
{
if (ps<a.size()&&(ps2==b.size()||a[ps].l<b[ps2].l))
{
if (d.r+1>=a[ps].l) d=d+a[ps];
else
{
if (d.l<=d.r) sp.push_back(d);
d=a[ps];
}
ps++;
}
else
{
if (d.r+1>=b[ps2].l) d=d+b[ps2];
else
{
if (d.l<=d.r) sp.push_back(d);
d=b[ps2];
}
ps2++;
}
}
sp.push_back(d);
return sp;
}
vector<reads>solve(int l,int r)
{
if (l==r) return DWP[l];
int mid=(l+r)>>1;
return solve(l,mid)+solve(mid+1,r);
}
void add(int x,int y)
{
E[x].push_back(y),E[y].push_back(x);
return;
}
void dfs(int x)
{
used[x]=sz[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i]])
{
fa[E[x][i]]=x,depth[E[x][i]]=depth[x]+1,ES[x].push_back(E[x][i]),dfs(E[x][i]),sz[x]+=sz[E[x][i]];
if (sz[E[x][i]]>sz[hs[x]]) hs[x]=E[x][i];
}
return;
}
void dfs2(int x)
{
int y=x;
vector<int>sp;
vector<int>tp;
while (y) dfn[y]=++leng,sp.push_back(y),top[y]=x,rev[dfn[y]]=y,y=hs[y];
for (int i=0;i<=3;++i)
{
tp.clear();
for (int j=0;j<sp.size();++j)
{
if (!num[sp[j]]) num[sp[j]]=++length;
for (int k=0;k<ES[sp[j]].size();++k) tp.push_back(ES[sp[j]][k]);
}
sp=tp;
}
y=x;
while (y)
{
for (int i=0;i<ES[y].size();++i)
if (ES[y][i]!=hs[y])
dfs2(ES[y][i]);
y=hs[y];
}
return;
}
void dfs3(int x)
{
for (int i=0;i<ES[x].size();++i)
{
if (ES[x][i]==hs[x])
{
for (int j=0;j<=3;++j) DP[ES[x][i]][j]=DP[ES[x][i]][j]+DP[x][j];
}
dfs3(ES[x][i]);
}
if (!ES[x].empty())
{
for (int i=0;i<ES[x].size();++i) DWP[i+1]=DP2[ES[x][i]];
DP2[x]=DP2[x]+solve(1,ES[x].size());
}
return;
}
struct seg
{
struct node
{
int l,r;
vector<reads>data;
};
node tree[(N<<2)+1];
void push_up(int k)
{
tree[k].data=tree[k<<1].data+tree[k<<1|1].data;
return;
}
void build(int k,int l,int r,int d)
{
tree[k].l=l,tree[k].r=r;
if (l==r)
{
tree[k].data=dp[rev[l]][d];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid,d),build(k<<1|1,mid+1,r,d),push_up(k);
return;
}
vector<reads>query(int k,int l,int r)
{
if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) return query(k<<1,l,r);
else if (l>=mid+1) return query(k<<1|1,l,r);
else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}
};
seg T[4];
struct seg2
{
struct node
{
int l,r;
long long lazy;
__int128 data;
};
node tree[(N<<2)+1];
void push_up(int k)
{
tree[k].data=tree[k<<1].data+tree[k<<1|1].data;
return;
}
void push_tag(int k,long long d)
{
tree[k].lazy+=d,tree[k].data+=(__int128)(d)*(tree[k].r-tree[k].l+1);
return;
}
void spread(int k)
{
if (tree[k].lazy!=0) push_tag(k<<1,tree[k].lazy),push_tag(k<<1|1,tree[k].lazy),tree[k].lazy=0;
return;
}
void build(int k,int l,int r)
{
tree[k].l=l,tree[k].r=r;
if (l==r) return;
int mid=(l+r)>>1;
build(k<<1,l,mid),build(k<<1|1,mid+1,r),push_up(k);
return;
}
void add(int k,int l,int r,int d)
{
if (tree[k].l==l&&tree[k].r==r)
{
push_tag(k,d);
return;
}
spread(k);
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) add(k<<1,l,r,d);
else if (l>=mid+1) add(k<<1|1,l,r,d);
else add(k<<1,l,mid,d),add(k<<1|1,mid+1,r,d);
push_up(k);
return;
}
__int128 query(int k,int l,int r)
{
if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
spread(k);
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) return query(k<<1,l,r);
else if (l>=mid+1) return query(k<<1|1,l,r);
else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}
};
seg2 T2;
vector<reads>get_path(int x,int y,int k)
{
vector<reads>sp;
while (top[x]!=top[y])
{
if (depth[top[x]]<depth[top[y]]) swap(x,y);
sp=sp+DP[x][k],x=fa[top[x]];
}
if (depth[x]>depth[y]) swap(x,y);
sp=sp+T[k].query(1,dfn[x],dfn[y]);
return sp;
}
void write(__int128 d)
{
if (!d) return;
write(d/10),printf("%d",(int)(d%10));
return;
}
void output(__int128 d)
{
if (d>0) write(d),puts("");
else if (d==0) puts("0");
else printf("-"),write(-d),puts("");
return;
}
int main()
{
int opt,x,y,d,k;
vector<reads>sp;
vector<int>zp;
n=read(),m=read();
for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
depth[1]=1,dfs(1),dfs2(1);
for (int i=1;i<=n;++i) dp[i][0]={(reads){num[i],num[i]}},rev2[num[i]]=i;
for (int i=1;i<=3;++i)
for (int j=1;j<=n;++j)
{
for (int t=0;t<E[j].size();++t) DWP[t+1]=dp[E[j][t]][i-1];
if (E[j].empty()) dp[j][i]=dp[j][i-1];
else dp[j][i]=dp[j][i-1]+solve(1,E[j].size());
}
for (int i=1;i<=n;++i)
{
for (int j=0;j<=3;++j) DP[i][j]=dp[i][j];
DP2[i]=dp[i][0];
}
dfs3(1);
for (int i=0;i<=3;++i) T[i].build(1,1,n,i);
T2.build(1,1,n);
for (int qt=1;qt<=m;++qt)
{
opt=read();
if (opt==1)
{
x=read(),y=read(),k=read(),d=read(),sp=get_path(x,y,k);
for (int i=0;i<sp.size();++i) T2.add(1,sp[i].l,sp[i].r,d);
}
else if (opt==2)
{
x=read(),d=read(),sp=DP2[x];
for (int i=0;i<sp.size();++i) T2.add(1,sp[i].l,sp[i].r,d);
}
else if (opt==3)
{
x=read(),y=read(),k=read(),sp=get_path(x,y,k),ans=0;
for (int i=0;i<sp.size();++i) ans+=T2.query(1,sp[i].l,sp[i].r);
printf("%llu\n",(unsigned long long)(ans));
}
else
{
x=read(),sp=DP2[x],ans=0;
for (int i=0;i<sp.size();++i) ans+=T2.query(1,sp[i].l,sp[i].r);
printf("%llu\n",(unsigned long long)(ans));
}
}
return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 48ms
memory: 174336kb
input:
5000 5000 1 2 2 3 3 4 4 5 5 6 5 7 6 8 7 9 9 10 8 11 11 12 12 13 12 14 14 15 15 16 16 17 16 18 18 19 18 20 20 21 20 22 22 23 23 24 23 25 23 26 26 27 27 28 28 29 27 30 30 31 29 32 32 33 33 34 32 35 35 36 36 37 35 38 36 39 38 40 38 41 41 42 42 43 43 44 42 45 44 46 45 47 47 48 48 49 48 50 49 51 51 52 52...
output:
37227703492 2136305359188 2794367845468 1309925069860 1698169768858 2678958746332 6690595071246 2087826052960 5786332239171 2186592622 4014965079076 1674542130 6524658548 7094033144666 10065416610040 11589693473717 492570862 3356228199498 2834694279 4198036633070 4395772262 4221137767 9630829210 992...
result:
ok 2559 numbers
Test #2:
score: 10
Accepted
time: 43ms
memory: 172384kb
input:
5000 5000 54 2 1945 3 4131 4 1207 5 3558 6 3582 7 1648 8 3498 9 1761 10 360 11 3617 12 4359 13 158 14 2314 15 529 16 4619 17 1070 18 1504 19 2675 20 2981 21 2142 22 1349 23 1640 24 1374 25 4059 26 2511 27 2708 28 2939 29 3017 30 3320 31 4602 32 4779 33 2697 34 3906 35 1121 36 197 37 1551 38 1119 39 ...
output:
0 198262395 0 0 1595057854 0 0 39277179818 13451201574 21469030838 0 0 23554220364 19140694248 212211615641 0 0 0 0 0 86500798 60136122614 47351162248 0 0 306346383502 230306838988 0 170207438 471673864986 387605196674 0 0 0 688392707 115968801311 199501119668 168720065378 634329317954 0 0 155717506...
result:
ok 2456 numbers
Subtask #2:
score: 10
Accepted
Test #3:
score: 10
Accepted
time: 1608ms
memory: 367660kb
input:
200000 200000 1 2 1 3 1 4 3 5 1 6 1 7 7 8 8 9 2 10 1 11 5 12 1 13 7 14 10 15 2 16 7 17 11 18 5 19 5 20 1 21 16 22 1 23 3 24 20 25 14 26 2 27 6 28 15 29 10 30 15 31 5 32 13 33 12 34 31 35 31 36 36 37 36 38 1 39 28 40 5 41 12 42 41 43 20 44 30 45 22 46 11 47 47 48 45 49 14 50 41 51 3 52 30 53 29 54 6 ...
output:
0 0 0 0 0 0 0 0 7615073807 4176911055 0 4745654848 6222845818 0 0 9739142819 0 1424960716 5224818790 9459319003 13717923473 8673060864 0 11610197664 0 0 9587792729 0 0 0 2747489046 12425650803 0 0 11191496476 0 37597503993 0 0 15164651949 14868775382 15559673116 0 16391028892 0 15726757336 0 2421390...
result:
ok 100169 numbers
Test #4:
score: 10
Accepted
time: 1772ms
memory: 357940kb
input:
200000 200000 121679 2 13340 3 45206 4 112138 5 47397 6 88216 7 173469 8 109861 9 58662 10 130056 11 61155 12 4313 13 196310 14 46189 15 32349 16 143798 17 103215 18 159921 19 27365 20 14332 21 49504 22 64451 23 106931 24 59878 25 177587 26 100555 27 86848 28 793 29 79845 30 150813 31 42854 32 11551...
output:
77900221111 0 0 476439705914 0 216029652830 0 0 631267909751 508097390689 0 29277716182 695169620128 0 809294022024 0 0 829507748883 260130797154 0 1005527232590 109198360548 821333235719 0 0 1265757368752 738460021055 296232170804 845184728833 0 434366813420 0 1922343637889 0 0 0 229703081048 0 441...
result:
ok 100073 numbers
Subtask #3:
score: 5
Accepted
Test #5:
score: 5
Accepted
time: 606ms
memory: 343376kb
input:
200000 200000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 ...
output:
0 134315201201061 38210069287857 75889674481730 25202765567748 179527420359031 75824479907233 156951577189979 246509811214535 251383387317167 181645886595511 285463150681348 213797241401335 244909583142805 53376921005282 451665818220 379334117147250 720759810155057 768646965102274 224741692238593 18...
result:
ok 100065 numbers
Test #6:
score: 5
Accepted
time: 614ms
memory: 343380kb
input:
200000 200000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 ...
output:
0 1950387013442 2906443199266 2144858813468 3137341049831 1081425884175 20924388962208 73530126133368 136609133052209 125022026678010 22502893517249 99022896674514 84010333777754 13909990392191 43442491331837 190816082733002 92810414504491 244006706308139 42843404030538 126151201042579 7249812065288...
result:
ok 99740 numbers
Subtask #4:
score: 10
Accepted
Test #7:
score: 10
Accepted
time: 1201ms
memory: 367492kb
input:
200000 200000 1 2 2 3 3 4 1 5 3 6 5 7 5 8 7 9 2 10 7 11 11 12 10 13 6 14 3 15 14 16 4 17 11 18 3 19 14 20 4 21 4 22 12 23 18 24 5 25 5 26 14 27 13 28 24 29 11 30 26 31 29 32 28 33 31 34 23 35 33 36 6 37 11 38 22 39 13 40 35 41 37 42 21 43 12 44 4 45 16 46 12 47 21 48 1 49 26 50 45 51 41 52 46 53 7 5...
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 99786 numbers
Test #8:
score: 10
Accepted
time: 775ms
memory: 357416kb
input:
200000 200000 1 2 2 3 1 4 1 5 2 6 3 7 6 8 8 9 8 10 9 11 8 12 12 13 13 14 11 15 13 16 13 17 16 18 17 19 18 20 19 21 19 22 21 23 21 24 21 25 24 26 23 27 26 28 27 29 26 30 30 31 28 32 29 33 32 34 32 35 33 36 36 37 35 38 38 39 38 40 40 41 39 42 42 43 43 44 41 45 45 46 43 47 45 48 46 49 49 50 50 51 51 52...
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 100404 numbers
Test #9:
score: 10
Accepted
time: 1195ms
memory: 358220kb
input:
200000 200000 166945 2 60190 3 101888 4 154621 5 188595 6 175999 7 140051 8 54071 9 167394 10 54228 11 48270 12 14564 13 25727 14 138072 15 77670 16 77795 17 155644 18 171648 19 94412 20 65323 21 130225 22 6359 23 17410 24 8580 25 142556 26 152863 27 166869 28 115234 29 87099 30 160349 31 98200 32 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 99768 numbers
Subtask #5:
score: 10
Accepted
Dependency #4:
100%
Accepted
Test #10:
score: 10
Accepted
time: 1253ms
memory: 365356kb
input:
200000 200000 1 2 1 3 2 4 1 5 2 6 2 7 2 8 5 9 3 10 10 11 5 12 4 13 5 14 9 15 11 16 14 17 12 18 13 19 2 20 16 21 3 22 16 23 2 24 7 25 8 26 20 27 21 28 11 29 12 30 4 31 2 32 21 33 14 34 29 35 16 36 21 37 28 38 22 39 27 40 12 41 36 42 32 43 30 44 3 45 43 46 4 47 14 48 44 49 9 50 37 51 20 52 11 53 31 54...
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 100258 numbers
Test #11:
score: 10
Accepted
time: 1243ms
memory: 358572kb
input:
200000 200000 184821 2 53793 3 183415 4 113765 5 178864 6 46342 7 933 8 197825 9 177971 10 143394 11 99313 12 188890 13 25495 14 60986 15 162307 16 135027 17 145920 18 109359 19 5215 20 75134 21 53020 22 160666 23 30142 24 23800 25 38903 26 121838 27 164296 28 86957 29 89705 30 108331 31 147730 32 2...
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 100336 numbers
Subtask #6:
score: 15
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #12:
score: 15
Accepted
time: 1193ms
memory: 367340kb
input:
200000 200000 1 2 1 3 2 4 2 5 5 6 3 7 2 8 3 9 4 10 7 11 9 12 7 13 2 14 12 15 6 16 5 17 14 18 3 19 14 20 13 21 8 22 7 23 12 24 5 25 3 26 18 27 9 28 8 29 6 30 22 31 5 32 6 33 28 34 19 35 24 36 24 37 35 38 7 39 32 40 20 41 19 42 14 43 1 44 5 45 30 46 9 47 30 48 5 49 44 50 7 51 13 52 11 53 19 54 31 55 4...
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 540038770 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100044 numbers
Test #13:
score: 15
Accepted
time: 852ms
memory: 325988kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 ...
output:
0 0 0 0 0 0 510 0 0 0 0 0 0 0 0 405 0 0 0 12322 0 1670 283520 0 0 0 0 0 407680 177845 0 405 0 0 0 0 1464 490 61 0 0 465860 0 16472 0 1534 265620 422870 767 0 0 0 788 280990 322 0 0 198 893 79486 0 767 0 0 0 0 0 0 40 1300 114170 14950 280978 0 0 58950 296946 436080 1512 9726 0 0 226707 325962 312984 ...
result:
ok 100096 numbers
Test #14:
score: 15
Accepted
time: 822ms
memory: 325892kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 ...
output:
0 0 0 0 304142 0 289115 0 224 0 576 637 154 0 0 0 0 364608 0 910496 333282 758 158646 0 1291 242188 365040 0 1333572 0 249 593761 180642 0 850 1186 0 89320 316618 704925 0 0 2475 148508 242 67518 979 0 67224 1692359 920722 3014 0 518286 0 1311330 1369518 1008436 3095052 511760 1650509 298410 1803117...
result:
ok 100062 numbers
Test #15:
score: 15
Accepted
time: 741ms
memory: 358928kb
input:
200000 200000 1 2 2 3 2 4 3 5 4 6 6 7 7 8 8 9 8 10 9 11 11 12 12 13 12 14 13 15 15 16 16 17 17 18 17 19 19 20 19 21 21 22 22 23 22 24 23 25 24 26 25 27 27 28 27 29 28 30 29 31 30 32 31 33 33 34 34 35 34 36 35 37 36 38 38 39 39 40 39 41 40 42 41 43 43 44 43 45 44 46 46 47 47 48 48 49 49 50 50 51 51 5...
output:
0 0 0 0 21346853945576 48396643270631 4321029030 37003305606483 17683419927060 561778302 94539925025025 561778302 19563617093670 0 17946414540 32901956622 13400634896 1907726287 290652131875362 498785221322560 566362662702578 553392549765534 3570739868 1016393566 16079113938 119565043564896 46196526...
result:
ok 100401 numbers
Test #16:
score: 15
Accepted
time: 1237ms
memory: 358056kb
input:
200000 200000 170804 2 114218 3 118786 4 81407 5 92607 6 121128 7 39792 8 17516 9 151784 10 45071 11 109409 12 10487 13 65474 14 193833 15 28336 16 144805 17 198454 18 107320 19 181481 20 138015 21 10446 22 181869 23 174873 24 194511 25 46182 26 42247 27 111765 28 80980 29 64828 30 33044 31 133963 3...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 536682891 0 0 0 0 0 0 0 0 0 894471485 0 0 0 0 0 0 0 0 0 0 0 1073365782 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 178894297 0 0 0 0 0 0 0 0 124910174 0 69868842 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1967837267 0 0 0 42599187462 0 536682891 0 0 0 0 0 687005957 0 0 0 562095783 0 0...
result:
ok 100179 numbers
Subtask #7:
score: 15
Accepted
Dependency #2:
100%
Accepted
Dependency #4:
100%
Accepted
Test #17:
score: 15
Accepted
time: 1716ms
memory: 367452kb
input:
200000 200000 1 2 1 3 3 4 1 5 2 6 3 7 1 8 5 9 6 10 9 11 2 12 8 13 3 14 4 15 12 16 10 17 2 18 2 19 14 20 12 21 9 22 19 23 14 24 3 25 13 26 21 27 11 28 5 29 9 30 13 31 13 32 4 33 6 34 14 35 14 36 31 37 13 38 10 39 4 40 28 41 13 42 14 43 20 44 37 45 8 46 14 47 32 48 21 49 40 50 46 51 20 52 44 53 15 54 ...
output:
0 12712803164 0 0 8193968417 14426787309 12950092190 0 32958618613 26764906955 8493139167 0 42785505564 55243799113 0 0 0 0 0 16857343623 27991363871 14151995536 55690427136 85838206842 0 26020925273 22490232861 0 0 1662166464 24948089565 0 26561191640 202942896717 0 91771091757 152033022013 2500525...
result:
ok 100098 numbers
Test #18:
score: 15
Accepted
time: 1306ms
memory: 323680kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 ...
output:
1506 2433795 1964764 29809 23904 32308 3956297 23683 26194 24496 0 5108618 44498 10494148 1493614 8948 11034059 10983525 9340774 68288 15623342 65908 14673691 63760 62016 68610 3785842 68409 71500 4760847 1843709 83560 86276 3800228 24415019 102280 92867 17894104 25995202 96677 14391781 110124 12872...
result:
ok 99928 numbers
Test #19:
score: 15
Accepted
time: 1709ms
memory: 339816kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 ...
output:
0 6432 5572 2146 5686 15024 5924 10437 10836 16481 12732 37909 15933 53994 38493 121364 89269 36850 69524 53517 239542 137860 93122 118688 151902 9279 120973 73158 28901 122575 43850 21781 119189 28818 71155 127221 157054 65948 40570 183418 150579 145757 147361 89223 4664 78041 329787 100673 50134 6...
result:
ok 100068 numbers
Subtask #8:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Dependency #7:
100%
Accepted
Test #20:
score: 25
Accepted
time: 1895ms
memory: 367504kb
input:
200000 200000 1 2 2 3 2 4 1 5 5 6 4 7 6 8 7 9 1 10 10 11 10 12 4 13 1 14 5 15 2 16 14 17 2 18 1 19 6 20 5 21 20 22 12 23 1 24 17 25 15 26 25 27 12 28 10 29 14 30 5 31 6 32 21 33 15 34 13 35 34 36 10 37 23 38 25 39 4 40 5 41 38 42 42 43 17 44 4 45 40 46 32 47 21 48 6 49 12 50 4 51 19 52 15 53 37 54 4...
output:
0 0 0 0 0 465548908352 0 0 1049072790058 0 0 0 3498253875794 2462272083501 0 0 0 6241645911240 0 494213688398 2347903181100 0 3728768281280 0 0 3432108986320 0 8469184085224 0 8245898092098 8330457266913 5826089812394 364325757 0 0 4349342792270 0 12318077513275 11118693711818 12376615187747 0 12897...
result:
ok 100329 numbers
Test #21:
score: 25
Accepted
time: 1121ms
memory: 357008kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 4 7 6 8 8 9 9 10 8 11 10 12 12 13 11 14 12 15 15 16 14 17 17 18 16 19 17 20 18 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 26 29 29 30 28 31 30 32 31 33 32 34 34 35 33 36 35 37 37 38 37 39 37 40 40 41 39 42 42 43 43 44 42 45 45 46 46 47 46 48 48 49 49 50 50 51 50 5...
output:
0 0 50569487 2600333591027 50569487 1186208456559 96537150683 291583662042 280086809868243 7561410184 182540503517537 3870048686 4825881401 568246059173105 508080241347192 638856244490679 7811085998489 398136386558692 259502453457033 596111245902764 135800450617255 496697642799696 148330538161166 62...
result:
ok 99764 numbers
Test #22:
score: 25
Accepted
time: 1993ms
memory: 358144kb
input:
200000 200000 99996 2 141376 3 146563 4 140743 5 137889 6 197771 7 6239 8 173333 9 147385 10 128295 11 87732 12 17498 13 966 14 58215 15 60811 16 196395 17 94285 18 143376 19 191265 20 18708 21 88524 22 83638 23 101810 24 133133 25 130094 26 147872 27 116578 28 153022 29 115586 30 18109 31 124747 32...
output:
0 1527305572085 620328030446 1252349895193 0 274142198558 723725574040 0 0 6748890038813 2520882634927 3368554730649 4584117267462 0 0 0 0 7844925682310 0 0 12178888018305 11389166537907 0 3557014247234 9922133339986 6339953599024 197496739660 0 2983329095305 206600063302 0 8481939789945 0 765606005...
result:
ok 100107 numbers
Test #23:
score: 25
Accepted
time: 1305ms
memory: 325892kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 ...
output:
423234 1110315 35538 0 3527944 4277944 3618216 1511552 9308952 0 12904322 0 22098641 663 622 28191749 26780936 9092662 0 36027851 0 1606 472358 1371 310 0 0 392 1501509 21987918 750 24841528 0 45565407 37148358 758 925 741 22914923 333 0 74918832 66975866 542 0 70139339 0 333 310 68455009 63979020 0...
result:
ok 99866 numbers
Test #24:
score: 25
Accepted
time: 1244ms
memory: 325864kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 ...
output:
0 0 0 0 2846778 470613 3342714 0 0 189 248 838 12429934 0 14013010 9028904 778 35 12146114 33379996 0 15999772 28982761 3771 1196 0 26539634 1366 56135190 1531 0 176 6547283 0 64019039 1883 2605 778 0 39362976 0 101259306 97083211 468 99564118 40791370 365 102820163 101082181 23 42949812 96099569 98...
result:
ok 100259 numbers
Test #25:
score: 25
Accepted
time: 1319ms
memory: 326084kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 ...
output:
0 0 1625022 0 0 0 0 6998162 1787351 0 3906102 4953087 0 4032292 0 0 1418 0 7039728 747 21958806 21557601 1138 17182376 7669849 26064810 0 17834813 0 5910523 0 32032298 26048645 11711702 3935933 0 36155896 51214723 59781840 60644963 65108813 21861955 5246285 800 0 9453207 26622210 45582424 292 430472...
result:
ok 100024 numbers
Test #26:
score: 25
Accepted
time: 1415ms
memory: 337500kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 ...
output:
0 0 0 0 0 0 0 79568 0 118118 0 0 222672 120434 108951 188357 108951 0 0 0 0 254819 0 0 0 292014 0 0 0 0 364782 31464 0 0 0 0 357975 0 0 183227 0 499201 240304 0 0 223898 24931 0 469642 0 0 468822 0 0 0 0 0 346464 23464 0 0 844602 0 0 0 0 1303492 0 0 1056750 1539022 0 0 0 837735 1545534 0 1130865 110...
result:
ok 100111 numbers
Test #27:
score: 25
Accepted
time: 1865ms
memory: 326524kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 ...
output:
0 19862670 17258551 455435 16488539 9130379 7314072 30575340 19690141 19313936 21669613 23012451 12837945 3723195 26457564 18702581 39548020 30336071 16441097 20939995 48290384 29762374 48067566 47812904 53042833 66100909 62174100 55375354 39831643 34875945 35403493 87775179 65358326 10922360 563282...
result:
ok 100383 numbers
Test #28:
score: 25
Accepted
time: 1736ms
memory: 323352kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 ...
output:
0 0 0 10733666 5512532 19003243 4619784 28471100 13929668 3288853 792985 37517085 25981724 17849894 29127734 4655989 39093189 16846305 18203668 25201100 30974270 20533921 25409377 21009591 61495726 45128919 54846665 4199447 27051769 67540627 26459973 95737163 58749670 70036821 64124214 66257942 4011...
result:
ok 100285 numbers