QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#762295 | #7767. 数据结构 | hxhhxh | 75 | 5605ms | 200156kb | C++20 | 3.9kb | 2024-11-19 14:27:59 | 2024-11-19 14:27:59 |
Judging History
answer
#include<bits/stdc++.h>
#define ll unsigned long long
#define pii pair<int,int>
#define vpi vector<pii>
#define fi first
#define se second
using namespace std;
const int N=2e5+5;
struct SEG{
struct st{
int l,r;
ll s,z;
}a[N<<2];
void bt(int x,int l,int r){
a[x].l=l;
a[x].r=r;
a[x].s=a[x].z=0;
if(l<r){
bt(x<<1,l,(l+r>>1));
bt(x<<1|1,(l+r>>1)+1,r);
}
}
void ps(int x,ll v){
a[x].s+=(a[x].r-a[x].l+1)*v;
a[x].z+=v;
}
void xf(int x){
ps(x<<1,a[x].z);
ps(x<<1|1,a[x].z);
a[x].z=0;
}
void pu(int x){
a[x].s=a[x<<1].s+a[x<<1|1].s;
}
void add(int x,int l,int r,ll v){
if(a[x].l==l&&a[x].r==r) return ps(x,v);
if(a[x].z) xf(x);
int mid=a[x].l+a[x].r>>1;
if(r<=mid) add(x<<1,l,r,v);
else if(l>mid) add(x<<1|1,l,r,v);
else add(x<<1,l,mid,v),add(x<<1|1,mid+1,r,v);
pu(x);
}
ll qs(int x,int l,int r){
if(a[x].l==l&&a[x].r==r) return a[x].s;
if(a[x].z) xf(x);
int mid=a[x].l+a[x].r>>1;
if(r<=mid) return qs(x<<1,l,r);
if(l>mid) return qs(x<<1|1,l,r);
return qs(x<<1,l,mid)+qs(x<<1|1,mid+1,r);
}
}T;
int n,Q,K,fa[N],dfn[N],hs[N],siz[N],dcnt,dep[N],top[N];
vector<int>e[N],g[N];
vpi tk[N][4],lk[N][4],tr[N];
void dfs1(int x,int f){
siz[x]=1;
dep[x]=dep[f]+1;
fa[x]=f;
for(int i:e[x]){
if(i==f) continue;
dfs1(i,x);
siz[x]+=siz[i];
g[x].push_back(i);
}
for(int i:g[x]) if(siz[i]>siz[hs[x]]) hs[x]=i;
}
void lb(int x){
if(!dfn[x]) dfn[x]=++dcnt;
}
void dfs2(int x,int ff){
top[x]=ff;
if(ff==x){
vector<int>u;
for(int t=x;t;t=hs[t]) u.push_back(t),lb(t);
for(int i=1;i<=3;i++){
vector<int>v;
for(int j:u) for(int l:g[j]) if(top[j]!=x) v.push_back(l),lb(l);
u=v;
}
}
if(hs[x]) dfs2(hs[x],ff);
for(int i:g[x]) if(i!=hs[x]) dfs2(i,i);
}
void zp(vpi&x){
sort(x.begin(),x.end());
vpi y;
for(pii i:x){
if(y.empty()||i.fi>y.back().se+1) y.push_back(i);
else y.back().se=max(y.back().se,i.se);
}
x=y;
}
void add(vpi&x,const vpi&y){
if(y.empty()) return;
if(x.empty()) x=y;
else{
for(pii i:y) x.push_back(i);
zp(x);
}
}
void dfs3(int x){
tr[x]=tk[x][0]={{dfn[x],dfn[x]}};
for(int i:g[x]){
dfs3(i);
for(int j=0;j<K;j++) add(tk[x][j+1],tk[i][j]);
add(tr[x],tr[i]);
}
for(int i=0;i<K;i++) add(tk[x][i+1],tk[x][i]);
}
void dfs4(int x){
for(int i=0;i<=K;i++) lk[x][i]=tk[x][i];
if(x>1) for(int i=0;i<K;i++) add(tk[x][i+1],tk[fa[x]][i]);
if(top[x]!=x) for(int i=0;i<=K;i++) add(lk[x][i],lk[fa[x]][i]);
for(int i:g[x]) dfs4(i);
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
vpi del(vpi a,vpi b){
vpi res;
int l=0,r=-1,m=b.size();
for(pii i:a){
while(l<m&&b[l].se<i.fi) l++;
while(r<m-1&&b[r+1].fi<=i.se) r++;
if(l>r){
res.push_back(i);
continue;
}
if(i.fi<b[l].fi) res.push_back({i.fi,b[l].fi-1});
for(int j=l+1;j<=r;j++) res.push_back({b[j-1].se+1,b[j].fi-1});
if(i.se>b[r].se) res.push_back({b[r].se+1,i.se});
}
zp(res);
return res;
}
vpi qw(int x,int k){
if(!x) return {};
vpi res=lk[x][k];
add(res,qw(fa[top[x]],k));
return res;
}
vpi ql(int x,int y,int k){
int u=lca(x,y);
vpi res=tk[u][k];
vpi wx=qw(u,k);
add(res,del(qw(x,k),wx));
add(res,del(qw(y,k),wx));
return res;
}
int main(){
// freopen("T2/zyf8.in","r",stdin);
// freopen("T2/zyf8.out","w",stdout);
cin>>n>>Q;K=3;
for(int i=1,j,k;i<n;i++){
scanf("%d %d",&j,&k);
e[j].push_back(k);
e[k].push_back(j);
}
dfs1(1,0);
dfs2(1,1);
dfs3(1);
dfs4(1);
T.bt(1,1,n);
for(int op,x,y,k,u;Q--;){
vpi cw;
scanf("%d",&op);
if(op&1) scanf("%d %d %d",&x,&y,&k),cw=ql(x,y,k);
else scanf("%d",&x),cw=tr[x];
ll res=0;
if(op<3){
scanf("%d",&u);
for(pii i:cw) T.add(1,i.fi,i.se,u);
}
else for(pii i:cw) res+=T.qs(1,i.fi,i.se);
if(op>2) printf("%lld\n",res);
}
return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 17ms
memory: 10368kb
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: 21ms
memory: 13988kb
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: 1066ms
memory: 172392kb
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: 1304ms
memory: 179824kb
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: 373ms
memory: 186780kb
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: 384ms
memory: 185584kb
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: 1838ms
memory: 171864kb
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: 597ms
memory: 194828kb
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: 1144ms
memory: 179256kb
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: 5605ms
memory: 172368kb
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: 1458ms
memory: 179480kb
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: 2744ms
memory: 172968kb
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: 1848ms
memory: 144484kb
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: 1523ms
memory: 146460kb
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: 526ms
memory: 200156kb
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: 1048ms
memory: 179324kb
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: 1399ms
memory: 172168kb
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: 1340ms
memory: 146088kb
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: 1582ms
memory: 169636kb
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: 0
Time Limit Exceeded
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: 0
Time Limit Exceeded
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...