QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #501053 | #9159. 登山 | tanxi# | 25 | 257ms | 26236kb | C++14 | 6.6kb | 2024-08-02 11:52:54 | 2024-08-02 11:52:55 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace A{
const int N=1e5+9,mod=998244353;
int dep[N],f[N],g[N],L[N],R[N],fa[N],d[N];
int dfn[N],siz[N],cnt,mp[N],mx[N],son[N];
struct xdt
{
int val[N<<2],sum[N<<2],lz[N<<2];
void pushup(int p)
{
val[p]=(val[p<<1]+val[p<<1|1])%mod;
sum[p]=(sum[p<<1]+sum[p<<1|1])%mod;
}
void pushdown(int p)
{
if(!lz[p])
return;
sum[p<<1]=(sum[p<<1]+lz[p]*val[p<<1]%mod+mod)%mod;
sum[p<<1|1]=(sum[p<<1|1]+lz[p]*(val[p<<1|1])%mod+mod)%mod;
lz[p<<1]+=lz[p];
lz[p<<1|1]+=lz[p];
lz[p]=0;
}
void update(int p,int l,int r,int x,int k)
{
if(l==r)
{
val[p]=k;sum[p]=0;
return;
}
pushdown(p);
int mid=(l+r)/2;
if(x<=mid)
update(p<<1,l,mid,x,k);
else
update(p<<1|1,mid+1,r,x,k);
pushup(p);
}
void add(int p,int l,int r,int L,int R,int k)
{
if(L>R)
return;
if(L<=l&&r<=R)
{
sum[p]=(sum[p]+val[p]*k%mod+mod)%mod;
lz[p]+=k;
return;
}
pushdown(p);
int mid=(l+r)/2;
if(L<=mid)
add(p<<1,l,mid,L,R,k);
if(R>mid)
add(p<<1|1,mid+1,r,L,R,k);
pushup(p);
}
int query(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
return sum[p];
}
int mid=(l+r)/2;
pushdown(p);
int now=0;
if(L<=mid)
now=(now+query(p<<1,l,mid,L,R))%mod;
if(R>mid)
now=(now+query(p<<1|1,mid+1,r,L,R))%mod;
return now;
}
}T;
int tr[N],ls[N],rs[N],dist[N];
int sz[N];
priority_queue<pair<int,int> >root;
void pushup(int p)
{
dist[p]=dist[rs[p]]+1;
sz[p]=sz[ls[p]]+sz[rs[p]]+1;
}
int merge(int x,int y)
{
if(!x||!y)
return x+y;
if(tr[x]<tr[y])
swap(x,y);
rs[x]=merge(rs[x],y);
if(dist[ls[x]]<dist[rs[x]])
swap(ls[x],rs[x]);
return x;
}
int del(int x)
{
int p=merge(ls[x],rs[x]);
ls[x]=rs[x]=tr[x]=dist[x]=0;
return p;
}
int n,fl;
struct bian
{
int to,lt;
}b[N<<1];
int head[N],top;
void mkb(int l,int r)
{
b[++top]={r,head[l]};
head[l]=top;
}
void dfs(int x)
{
siz[x]=1;
dfn[x]=++cnt;
mp[cnt]=x;
son[x]=0;
for(int t=head[x];t;t=b[t].lt)
{
int y=b[t].to;
dfs(y);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]])
son[x]=y;
}
}
struct Cao
{
int opt,l,r,k;
}stk[N*30];
int tp;
void dsu(int x,bool flag)
{
for(int t=head[x];t;t=b[t].lt)
{
int y=b[t].to;
if(y==son[x])
continue;
dsu(y,false);
}
if(son[x])
{
dsu(son[x],true);
}
int rt=x,rd=d[x];
ls[x]=rs[x]=0;
tr[x]=L[x];
sz[x]=1;
vector<int>nd;
nd.clear();
while(!root.empty()&&root.top().first>rd)
{
int p=root.top().second;
while(tr[p]>rd)
{
stk[++tp]={1,tr[p],root.top().first,1};
p=del(p);
}
stk[++tp]={1,rd+1,root.top().first,sz[p]};
if(p)
{
nd.push_back(p);
}
root.pop();
}
int p=0;
for(auto u:nd)
{
p=merge(p,u);
}
if(p)
root.push({rd,p});
if(min(rd,R[x])>=L[x])
{
stk[++tp]={1,L[x],min(rd,R[x]),-1};
root.push({min(rd,R[x]),x});
}
mx[x]=d[x];
for(int t=head[x];t;t=b[t].lt)
{
int y=b[t].to;
if(y==son[x])
continue;
for(int i=dfn[y];i<dfn[y]+siz[y];i++)
{
mx[mp[i]]=min(mx[fa[mp[i]]],d[mp[i]]);
if(L[mp[i]]<=min(mx[mp[i]],R[mp[i]]))
{
tr[mp[i]]=L[mp[i]];
ls[mp[i]]=rs[mp[i]]=0;
sz[mp[i]]=1;
stk[++tp]={1,L[mp[i]],min(mx[mp[i]],R[mp[i]]),-1};
root.push({min(mx[mp[i]],R[mp[i]]),mp[i]});
}
}
}
stk[++tp]={3,dep[x],dep[x],x};
stk[++tp]={2,1,n,x};
if(!flag)
{
while(!root.empty())
{
int p=root.top().second;
int t=root.top().first;
while(p)
{
stk[++tp]={1,tr[p],t,1};
p=del(p);
}
root.pop();
}
}
}
signed mian(int id,int td)
{
// freopen("ex_2.in","r",stdin);
// freopen("mountain.out","w",stdout);
// cin>>id>>td;
while(td--)
{
cnt=0;
memset(head,0,sizeof(head));
top=0;
cin>>n;
memset(f,0,sizeof(f));
dep[1]=0;
for(int i=2;i<=n;i++)
{
cin>>fa[i];
mkb(fa[i],i);
dep[i]=dep[fa[i]]+1;
int l,r;
cin>>l>>r;
L[i]=dep[i]-r;
R[i]=dep[i]-l;
cin>>d[i];
d[i]=dep[i]-d[i]-1;
L[i]++;
R[i]++;
d[i]++;
}
L[1]=114514;
R[1]=0;
for(int i=1;i<=n;i++)
dep[i]++;
dfs(1);
dsu(1,false);
f[1]=1;
while(tp)
{
if(stk[tp].opt==1)
{
T.add(1,1,n,stk[tp].l,stk[tp].r,stk[tp].k);
}
if(stk[tp].opt==2)
{
f[stk[tp].k]=T.query(1,1,n,1,n);
}
if(stk[tp].opt==3)
{
T.update(1,1,n,stk[tp].l,f[stk[tp].k]);
}
f[1]=1;
tp--;
}
for(int i=2;i<=n;i++)
cout<<f[i]<<' ';
cout<<'\n';
}
return 0;
}
}
namespace B
{
const int N=1e5+9,mod=998244353;
int dep[N],f[N],g[N],L[N],R[N],fa[N],d[N];
int dfn[N],siz[N],cnt,mp[N],mx[N];
int id,T,n,fl;
struct bian
{
int to,lt;
}b[N<<1];
int head[N],top;
void mkb(int l,int r)
{
b[++top]={r,head[l]};
head[l]=top;
}
void dfs(int x)
{
siz[x]=1;
dfn[x]=++cnt;
mp[cnt]=x;
for(int t=head[x];t;t=b[t].lt)
{
int y=b[t].to;
dfs(y);
siz[x]+=siz[y];
}
}
void dp(int x)
{
if(x==1)
f[x]=1;
else
{
if(fl)
{
f[x]=(g[R[x]]-(L[x]?g[L[x]-1]:0)+mod)%mod*siz[x]%mod;
}
else
{
mx[x]=d[x];
int mmx=min(R[x],d[x]);
f[x]=mmx>=L[x]?(g[mmx]-(L[x]?g[L[x]-1]:0)+mod)%mod:0;
for(int i=dfn[x]+1;i<dfn[x]+siz[x];i++)
{
mx[mp[i]]=min(d[mp[i]],mx[fa[mp[i]]]);
int mmx=min(R[mp[i]],mx[mp[i]]);
f[x]=(f[x]+(mmx>=L[mp[i]]?(g[mmx]-(L[mp[i]]?g[L[mp[i]]-1]:0)+mod)%mod:0))%mod;
}
}
}
g[dep[x]]=f[x];
if(dep[x])
g[dep[x]]=(g[dep[x]-1]+g[dep[x]])%mod;
for(int t=head[x];t;t=b[t].lt)
{
int y=b[t].to;
dp(y);
}
}
signed mian(int id,int T)
{
// freopen("ex_1.in","r",stdin);
// freopen("mountain.out","w",stdout);
if(id<=5||id==6||id==7||id==10||id==11||id==12)
{
if(id>5)
fl=1;
while(T--)
{
cnt=0;
memset(head,0,sizeof(head));
top=0;
cin>>n;
memset(f,0,sizeof(f));
for(int i=2;i<=n;i++)
{
cin>>fa[i];
mkb(fa[i],i);
dep[i]=dep[fa[i]]+1;
int l,r;
cin>>l>>r;
L[i]=dep[i]-r;
R[i]=dep[i]-l;
cin>>d[i];
d[i]=dep[i]-d[i]-1;
}
dfs(1);
dp(1);
for(int i=2;i<=n;i++)
cout<<f[i]<<' ';
cout<<'\n';
}
return 0;
}
return 0;
}
}
int id,t;
signed main()
{
cin>>id>>t;
if(t>5)
A::mian(id,t);
else
B::mian(id,t);
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 18336kb
input:
1 4 6 1 1 1 0 1 1 1 0 3 1 2 1 3 2 2 0 4 2 3 1 6 1 1 1 0 2 1 2 0 2 1 2 0 1 1 1 0 4 1 2 2 6 1 1 1 0 1 1 1 0 3 1 2 1 4 2 2 0 3 1 1 0 6 1 1 1 0 1 1 1 0 3 1 1 0 4 2 3 1 2 1 2 0
output:
1 4 2 1 5 3 4 4 1 0 1 2 1 2 2 2 2 5 3 3
result:
ok 20 numbers
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 18472kb
input:
2 4 300 1 1 1 0 2 1 2 1 3 1 3 1 1 1 1 0 3 1 3 0 4 2 2 3 7 1 2 0 8 2 2 2 7 1 3 4 7 3 4 4 11 1 6 1 12 1 3 5 10 2 5 5 13 1 5 4 13 4 7 2 15 8 8 8 16 8 9 4 15 1 9 6 18 4 5 6 19 3 8 8 18 5 10 2 19 3 7 5 23 5 7 6 22 6 8 10 23 4 7 3 24 1 4 6 24 8 12 9 28 7 11 8 26 1 9 7 28 1 3 1 29 2 5 0 32 1 6 4 30 5 12 7 ...
output:
19 18 35 1 38 15 50 0 0 15 349 261 0 525 195 0 108 490 0 0 103 632 393 0 814 0 378 625 174 1025 6236 3125 139 2003 1218 1935 37 265 1218 3929 19 0 211 0 19 1135 35695 14466 46868 29814 18352 5053 11375 28739 0 27114 13392 7593 423 2714 22394 22394 15506 1218 8147 13088 0 17493 42846 178996 171635 9 ...
result:
ok 1196 numbers
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 16692kb
input:
3 4 300 1 1 1 0 2 1 2 1 3 3 3 0 2 1 2 1 3 1 3 1 3 1 3 0 4 1 4 1 6 4 4 2 9 3 5 1 7 3 4 2 10 2 5 4 12 1 5 2 11 1 3 2 12 3 6 6 13 6 6 3 13 3 8 0 14 3 5 0 16 3 5 5 16 6 9 5 20 2 7 3 20 3 7 9 21 7 9 2 23 3 4 8 21 4 9 6 24 11 12 2 25 3 4 1 27 7 13 5 26 1 8 3 29 2 4 6 29 6 15 14 29 5 5 10 32 6 10 11 30 1 9...
output:
20 18 40 1 233 80 39 212 229 41 190 5094 56 0 4147 713 118 0 4129 5124 0 3313 2850 947 21534 9179 903 21496 2811 1 0 0 2811 143571 56660 67998 10105 25021 67687 3214 0 0 82668 44365 27652 38 25699 379349 23912 1787 84893 13400 25076 13513 0 3370 24657 0 24275 58446 49516 740 0 1198 48652 0 942 256 1...
result:
ok 1196 numbers
Pretest #4:
score: 5
Accepted
time: 68ms
memory: 17080kb
input:
4 4 5000 1 1 1 0 1 1 1 0 1 1 1 0 4 1 2 0 5 2 3 2 5 1 3 1 6 2 3 2 6 2 3 1 8 3 5 4 8 4 5 3 11 2 4 4 11 1 3 3 11 5 6 3 12 1 1 6 15 1 5 3 15 1 6 6 17 5 6 5 17 6 8 4 18 7 9 3 19 1 10 3 19 2 4 7 20 1 9 3 23 8 11 7 22 2 5 4 23 7 8 1 24 1 9 8 26 9 11 7 28 8 10 13 29 1 11 3 30 9 9 14 31 11 15 4 32 8 16 8 31 ...
output:
1 1 28 83 25 29 108 111 1 79 21 0 29 21 133 133 533 381 1227 345 0 1112 352 21 423 108 236 20 3618 384 2884 2568 2114 0 7325 1427 7325 3531 1211 1211 19325 28 27101 28 25566 28 18010 0 4297 10182 0 104310 18494 85683 1003 13578 130166 229 28179 27681 117683 173543 113521 3918 9870 4030 1902 0 0 2142...
result:
ok 19996 numbers
Pretest #5:
score: 5
Accepted
time: 78ms
memory: 14780kb
input:
5 4 5000 1 1 1 0 1 1 1 0 1 1 1 0 2 1 2 0 3 1 1 1 4 1 1 0 6 1 3 2 7 1 3 1 8 2 2 0 8 1 3 2 11 3 5 1 10 1 5 4 13 1 2 4 12 3 4 3 15 3 5 2 15 2 6 2 15 1 3 3 16 7 7 3 19 1 7 4 18 2 3 4 20 1 10 5 21 2 3 8 21 4 9 6 22 7 9 3 24 2 6 8 25 1 3 4 25 3 4 1 26 3 4 3 29 5 11 9 28 8 11 12 29 7 9 11 32 5 12 5 32 11 1...
output:
2 35 2 3 34 5 34 3 35 277 514 1 0 444 1451 380 134 1106 1071 134 726 0 134 345 64 0 2177 232 69 0 29 1472 1695 0 1625 0 0 1589 0 4219 2460 104 68 725 1235 1337 15332 1171 0 16744 9322 1360 13966 22157 3645 2319 16617 4491 15278 7736 1339 7806 9758 10865 1339 28395 22817 4866 1338 36 4422 64 5226 325...
result:
ok 19996 numbers
Pretest #6:
score: 0
Wrong Answer
time: 237ms
memory: 26236kb
input:
6 4 100000 1 1 1 0 2 1 1 0 3 1 1 0 4 2 2 0 5 1 1 0 6 2 2 0 7 6 6 0 8 3 3 0 9 6 6 0 10 8 8 0 11 6 6 0 12 12 12 0 13 11 11 0 14 2 2 0 15 2 2 0 16 2 2 0 17 9 9 0 18 1 1 0 19 4 4 0 20 18 18 0 21 13 13 0 22 20 20 0 23 3 3 0 24 21 21 0 25 8 8 0 26 11 11 0 27 11 11 0 28 3 3 0 29 21 21 0 30 1 1 0 31 27 27 0...
output:
99999 17256472 629188600 611932128 769033519 157101391 16756477 440631552 843443481 508393296 130019701 99988 456623880 14956638 833157345 54452998 146432667 379230896 406230007 335828576 380395165 301315632 182973950 389813658 352446580 563594710 403112145 756812272 848320161 717486055 830707839 70...
result:
wrong answer 1st numbers differ - expected: '7', found: '99999'
Pretest #7:
score: 0
Wrong Answer
time: 247ms
memory: 21688kb
input:
7 4 100000 1 1 1 0 1 1 1 0 1 1 1 0 3 1 1 0 1 1 1 0 3 1 1 0 7 1 1 0 6 1 1 0 9 2 2 0 6 1 1 0 6 1 1 0 7 2 2 0 9 2 2 0 11 1 1 0 11 2 2 0 14 4 4 0 12 1 1 0 16 3 3 0 15 1 1 0 17 3 3 0 20 5 5 0 18 4 4 0 20 2 2 0 19 2 2 0 22 5 5 0 22 2 2 0 22 3 3 0 23 5 5 0 27 7 7 0 26 6 6 0 27 5 5 0 31 1 1 0 33 9 9 0 34 2 ...
output:
1 5 1 5 99992 15 15 499960 99992 14956614 399968 5 299976 960558051 299976 2 1199904 199984 609017521 499960 99975 2 960558051 299976 13756710 828808210 960558051 1 1 13656718 14956614 634754473 7 634754473 271264593 99960 14956614 27513420 1 27513420 10357645 772126541 428203839 439581378 14956614 ...
result:
wrong answer 2nd numbers differ - expected: '1', found: '5'
Pretest #8:
score: 0
Wrong Answer
time: 1ms
memory: 5596kb
input:
8 4 100000 1 1 1 0 2 2 2 0 3 3 3 0 4 4 4 2 5 2 2 1 6 6 6 0 7 2 2 0 8 7 7 3 9 4 4 3 10 1 1 4 11 3 3 0 12 8 8 11 13 13 13 7 14 5 5 10 15 8 8 11 16 14 14 5 17 9 9 2 18 17 17 7 19 3 3 1 20 1 1 9 21 14 14 5 22 5 5 17 23 8 8 14 24 8 8 9 25 24 24 7 26 24 24 7 27 17 17 8 28 27 27 27 29 26 26 6 30 17 17 14 3...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Pretest #9:
score: 0
Wrong Answer
time: 1ms
memory: 5648kb
input:
9 4 100000 1 1 1 0 2 2 2 0 2 1 1 1 2 2 2 1 1 1 1 0 6 1 1 1 3 1 1 0 6 1 1 0 7 1 1 2 6 2 2 0 8 3 3 2 9 1 1 1 9 1 1 0 12 5 5 2 14 1 1 3 13 4 4 3 13 1 1 3 14 3 3 3 17 5 5 2 19 1 1 0 18 3 3 3 22 3 3 5 23 1 1 0 21 5 5 3 22 4 4 4 23 7 7 2 24 6 6 3 25 2 2 1 29 6 6 7 29 8 8 3 31 8 8 7 32 6 6 5 31 5 5 7 31 2 ...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Pretest #10:
score: 0
Wrong Answer
time: 237ms
memory: 26148kb
input:
10 4 100000 1 1 1 0 2 2 2 0 3 3 3 0 4 2 2 0 5 2 4 0 6 1 3 0 7 2 4 0 8 3 8 0 9 1 6 0 10 4 6 0 11 2 9 0 12 2 3 0 13 1 13 0 14 4 12 0 15 1 9 0 16 7 13 0 17 10 17 0 18 17 17 0 19 10 11 0 20 2 13 0 21 9 11 0 22 15 18 0 23 9 22 0 24 4 6 0 25 21 22 0 26 9 16 0 27 18 27 0 28 4 16 0 29 13 24 0 30 1 5 0 31 5 ...
output:
99999 99998 99997 16956478 50569440 78497288 10871373 974802767 582313009 538460962 628542991 38500215 943710298 722189889 567470325 27689563 425998610 15656488 794328141 51602878 72764311 592700573 318470792 565623815 219733201 498336655 168631392 917765419 945495513 219051459 855965601 56283786 83...
result:
wrong answer 1st numbers differ - expected: '27', found: '99999'
Pretest #11:
score: 0
Wrong Answer
time: 247ms
memory: 21460kb
input:
11 4 100000 1 1 1 0 1 1 1 0 2 1 2 0 1 1 1 0 2 1 2 0 6 1 3 0 5 1 2 0 7 2 3 0 6 2 2 0 8 1 3 0 9 2 3 0 9 3 5 0 10 2 4 0 13 2 4 0 12 4 6 0 13 1 6 0 16 1 4 0 18 6 7 0 18 2 4 0 20 1 6 0 21 2 9 0 20 1 3 0 23 1 4 0 22 1 8 0 24 10 10 0 23 3 5 0 24 3 11 0 26 8 11 0 27 1 9 0 30 2 11 0 28 12 12 0 32 4 8 0 32 9 ...
output:
99995 1 99996 3 16456498 394697786 8 378041303 199990 12 560384847 49669482 16556494 789195587 295358822 838965065 948152696 16556493 4096616 754485739 203355361 488261215 276880292 543840111 199990 420467330 593817309 789295582 24123755 511284049 99969 158688516 378041303 189545578 362866896 536844...
result:
wrong answer 1st numbers differ - expected: '41', found: '99995'
Pretest #12:
score: 0
Wrong Answer
time: 246ms
memory: 22140kb
input:
12 4 100000 1 1 1 0 1 1 1 0 3 1 2 0 3 1 2 0 4 1 1 0 4 1 3 0 6 2 4 0 7 2 4 0 9 1 4 0 8 1 3 0 11 3 3 0 11 5 6 0 12 1 2 0 14 3 3 0 13 2 7 0 16 2 3 0 17 2 4 0 17 7 9 0 17 3 8 0 20 2 6 0 21 10 11 0 21 6 11 0 21 7 9 0 23 3 4 0 24 5 11 0 26 6 9 0 26 5 7 0 27 12 13 0 29 10 10 0 28 1 3 0 31 13 15 0 32 7 13 0...
output:
1 99998 17056474 99999 509593284 51469419 509093289 34312946 102938837 88623192 530535499 16056484 240073029 88623192 490061099 698928332 594740775 17156473 151480758 178707459 99999 252443770 561885829 850409090 321582188 316769133 518404072 34312944 88623192 629775307 131650883 49412359 74997388 5...
result:
wrong answer 2nd numbers differ - expected: '44', found: '99998'
Pretest #13:
score: 0
Wrong Answer
time: 1ms
memory: 5628kb
input:
13 4 100000 1 1 1 0 2 1 2 0 3 2 2 2 4 2 4 1 5 1 2 4 6 4 6 2 7 1 6 4 8 6 6 5 9 5 8 8 10 6 6 1 11 8 11 5 12 8 11 1 13 4 8 6 14 4 7 1 15 11 15 5 16 1 1 10 17 6 9 7 18 8 16 2 19 2 9 10 20 6 20 7 21 12 14 11 22 9 14 14 23 6 7 22 24 12 14 11 25 20 20 21 26 10 20 0 27 19 26 8 28 21 23 12 29 4 13 23 30 15 2...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Pretest #14:
score: 0
Wrong Answer
time: 1ms
memory: 5860kb
input:
14 4 100000 1 1 1 0 2 1 1 1 1 1 1 0 2 1 2 1 4 2 2 1 5 2 2 1 7 1 4 1 8 2 5 3 8 5 5 3 10 2 3 5 11 1 6 5 10 1 4 5 12 5 8 1 12 3 6 5 13 3 6 2 15 2 5 8 17 6 7 6 18 6 8 5 17 10 10 1 18 4 5 5 20 4 11 7 22 8 9 4 23 9 13 12 24 9 13 10 24 6 8 7 26 3 13 13 26 11 14 11 28 11 11 2 27 9 16 8 30 6 12 0 31 13 17 16...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Pretest #15:
score: 0
Wrong Answer
time: 1ms
memory: 5524kb
input:
15 4 100000 1 1 1 0 1 1 1 0 3 1 1 1 3 2 2 0 4 1 2 0 5 1 1 2 2 1 2 0 3 1 2 0 7 3 3 1 9 3 3 1 8 1 2 1 10 1 5 1 8 2 3 0 9 1 2 1 11 3 3 3 14 1 2 2 15 1 3 1 15 2 4 0 15 1 4 3 17 3 4 2 19 5 5 2 21 4 6 4 21 6 6 2 24 2 4 6 24 3 7 4 22 3 4 0 23 1 5 5 23 5 6 6 26 2 8 3 30 5 9 8 27 4 6 1 27 3 7 2 31 6 8 7 32 5...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Pretest #16:
score: 0
Wrong Answer
time: 1ms
memory: 5568kb
input:
16 4 100000 1 1 1 0 1 1 1 0 1 1 1 0 4 1 1 1 1 1 1 0 2 1 2 0 7 2 3 2 3 2 2 0 6 2 2 0 8 2 3 0 11 1 5 1 11 2 5 3 11 3 3 4 14 2 6 2 14 2 3 0 12 2 3 0 12 4 5 0 16 3 7 1 19 3 7 2 18 3 4 2 21 2 4 0 22 1 3 0 21 1 6 6 21 4 5 3 21 1 7 4 23 1 10 2 26 1 6 4 23 9 10 0 25 7 8 1 25 3 9 2 27 9 11 3 29 4 11 7 33 2 6...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Pretest #17:
score: 0
Wrong Answer
time: 1ms
memory: 5648kb
input:
17 4 100000 1 1 1 0 2 2 2 0 1 1 1 0 1 1 1 0 5 1 2 1 5 1 2 1 6 2 2 2 7 1 1 0 8 1 1 3 8 3 4 2 6 1 3 2 9 2 4 1 8 4 4 0 11 1 4 2 10 3 3 1 11 2 5 0 14 2 3 0 17 4 4 2 14 3 4 4 17 1 4 2 19 2 6 6 17 1 1 5 18 1 5 3 23 3 7 2 22 2 3 7 24 4 6 3 23 1 7 4 23 7 7 5 27 5 6 2 26 6 9 5 28 1 7 4 30 1 9 5 29 2 6 6 29 4...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Pretest #18:
score: 0
Wrong Answer
time: 1ms
memory: 5820kb
input:
18 4 100000 1 1 1 0 2 1 2 1 2 1 2 0 2 1 2 0 3 3 3 1 5 1 3 1 4 2 3 2 7 1 3 1 8 2 4 0 9 1 4 1 8 2 3 3 12 2 5 3 9 2 3 2 11 1 1 1 11 2 4 1 14 1 6 2 15 7 7 0 17 2 4 4 18 6 7 1 17 2 6 6 17 5 5 1 20 2 5 7 22 1 7 3 23 6 10 7 25 4 4 6 25 8 11 7 26 2 10 3 26 6 7 6 27 12 12 2 28 1 1 0 29 8 11 11 32 3 9 12 30 2...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Pretest #19:
score: 0
Wrong Answer
time: 1ms
memory: 5464kb
input:
19 4 100000 1 1 1 0 1 1 1 0 2 1 1 1 4 1 3 1 1 1 1 0 6 2 2 1 5 2 2 1 6 1 1 0 5 2 3 1 9 1 3 0 10 1 5 3 11 2 4 1 10 2 5 2 13 1 2 2 15 1 3 0 16 1 3 1 16 3 4 6 14 6 6 0 18 6 6 1 19 1 7 2 21 6 6 4 20 9 9 3 21 1 4 5 22 4 8 7 24 2 9 8 26 7 8 0 25 1 2 8 28 1 9 8 26 2 5 3 30 2 2 1 27 9 9 3 30 4 9 2 29 3 7 8 3...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Pretest #20:
score: 0
Wrong Answer
time: 1ms
memory: 5824kb
input:
20 4 100000 1 1 1 0 2 1 1 0 3 1 3 2 4 4 4 1 5 1 5 0 6 1 6 3 4 2 2 1 3 3 3 2 8 1 1 3 7 2 5 0 10 1 3 4 11 1 7 5 9 1 1 3 14 1 3 1 12 4 6 4 16 1 4 7 15 2 4 4 17 2 7 1 19 6 9 6 18 4 6 2 18 2 7 4 18 2 4 3 22 1 7 0 19 3 9 6 20 4 7 7 26 5 10 9 27 2 7 10 27 3 10 6 29 8 9 10 26 7 8 5 31 3 9 1 31 5 13 5 32 10 ...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 18536kb
input:
1 4 6 1 1 1 0 2 1 2 0 3 2 3 0 3 2 2 2 5 4 4 3 6 1 1 1 0 1 1 1 0 3 1 1 1 3 1 1 0 4 2 3 1 6 1 1 1 0 2 1 2 1 2 1 2 0 2 2 2 0 2 1 2 0 6 1 1 1 0 2 1 1 1 1 1 1 0 4 1 2 1 5 1 2 2
output:
4 11 5 1 1 1 2 1 2 3 5 1 6 1 6 1 0 2 1 0
result:
ok 20 numbers
Test #2:
score: 5
Accepted
time: 0ms
memory: 14636kb
input:
2 4 300 1 1 1 0 2 1 1 0 1 1 1 0 4 1 2 1 2 2 2 0 6 1 2 1 3 1 3 0 4 1 2 1 6 1 1 1 10 2 3 0 6 2 3 2 11 2 4 0 11 4 5 2 14 4 4 5 10 1 3 2 12 3 4 0 12 2 4 1 15 7 7 5 17 3 4 1 16 4 4 0 21 2 2 5 20 2 4 2 20 2 2 1 23 3 5 1 20 3 4 0 22 4 5 0 26 5 7 1 28 1 8 1 27 2 6 6 26 1 5 2 30 1 3 6 28 1 1 4 28 2 7 6 34 2 ...
output:
34 69 3 1 236 34 104 1 173 749 28 443 36 1 69 2124 271 1 2089 35 1 528 2124 2388 7628 444 4976 12140 35 2388 271 0 193 298 1 444 1 388 0 0 22121 5170 2423 89 9981 236 4511 29441 0 0 28 17308 12797 20 290 0 28 66702 24245 47192 29221 238597 12140 15625 92547 8753 45281 107649 11412 4241 91539 477 118...
result:
ok 1196 numbers
Test #3:
score: 5
Accepted
time: 4ms
memory: 18120kb
input:
3 4 300 1 1 1 0 2 1 2 0 3 1 3 0 4 1 3 2 4 1 4 2 3 1 2 0 5 1 5 0 4 1 2 3 4 1 4 3 5 1 2 2 8 5 6 3 10 1 3 2 9 4 5 3 13 4 6 1 10 1 4 3 12 4 5 5 13 1 2 1 13 2 3 4 18 6 7 6 17 6 8 3 19 1 3 3 21 9 9 4 22 2 4 5 21 5 7 4 22 1 5 1 23 3 9 3 24 1 1 6 25 1 2 7 28 1 8 6 30 1 11 2 30 4 9 0 32 2 10 3 30 6 8 8 32 6 ...
output:
25 249 447 129 26 274 929 1 16 0 78 1288 26 275 25 52 17 763 1 1951 3700 851 3253 825 2514 1857 3253 0 6382 19019 20093 9716 823 3914 2067 9277 585 8365 79274 36681 2789 274 274 22165 72494 0 53117 0 2789 300999 0 41180 139365 6759 0 6759 1288 46560 278623 56757 709247 195711 80845 3914 37444 36895 ...
result:
ok 1196 numbers
Test #4:
score: 5
Accepted
time: 67ms
memory: 17088kb
input:
4 4 5000 1 1 1 0 2 1 2 1 1 1 1 0 4 1 1 0 1 1 1 0 3 2 3 2 6 1 2 1 5 1 2 0 8 3 3 1 10 1 3 2 8 2 2 0 11 1 5 4 11 3 5 3 13 4 5 3 12 3 3 1 16 1 5 1 13 4 5 5 18 1 5 5 17 1 6 5 17 1 5 4 20 5 7 4 19 1 1 7 23 1 8 3 23 4 6 4 23 8 9 7 24 3 4 2 27 3 6 3 28 5 8 9 26 1 4 4 27 3 10 8 28 8 11 9 31 4 6 3 31 10 10 2 ...
output:
3 2 1 2 41 1 40 3 118 117 207 34 42 81 166 332 33 33 2 41 82 33 3462 235 42 3244 221 0 0 2957 121 99 6338 2342 40 1974 6298 375 11832 39000 0 18301 22749 1315 5762 0 14123 4460 5795 548 0 0 5520 548 33 548 106 9048 0 40 158 0 5137 5137 0 14387 0 30149 9193 2957 160 375 2 82113 375 384 14939 7233 711...
result:
ok 19996 numbers
Test #5:
score: 5
Accepted
time: 64ms
memory: 16744kb
input:
5 4 5000 1 1 1 0 2 2 2 1 3 1 2 2 1 1 1 0 3 1 1 0 4 2 2 3 5 1 1 1 8 3 3 1 8 2 3 2 6 4 4 3 10 2 4 2 10 2 4 2 12 4 5 3 11 2 3 4 11 5 5 1 14 1 3 5 16 1 1 2 15 1 3 0 17 1 4 2 18 3 7 3 21 5 8 6 18 6 7 2 22 1 5 5 24 4 7 4 21 5 7 7 24 2 9 0 26 9 9 2 24 5 9 9 29 8 11 2 30 3 7 4 30 8 9 6 31 5 10 6 30 3 5 4 34...
output:
34 33 0 6 65 0 5 1 4 32 14 7 7 0 265 0 264 97 18 229 95 35 223 362 1 1017 1 26 5427 3593 823 2835 878 132 2209 1314 588 24 1550 429 24 7761 264 0 24 1068 837 0 495 1018 8258 430 194 229 34 7967 324 21377 229 14847 1266 0 583 5055 547 0 45349 4362 6902 90 693 16835 10064 693 54761 4611 37001 10523 58...
result:
ok 19996 numbers
Test #6:
score: 0
Wrong Answer
time: 257ms
memory: 25296kb
input:
6 4 100000 1 1 1 0 2 2 2 0 3 2 2 0 4 2 2 0 5 3 3 0 6 3 3 0 7 6 6 0 8 3 3 0 9 5 5 0 10 2 2 0 11 4 4 0 12 6 6 0 13 8 8 0 14 6 6 0 15 2 2 0 16 2 2 0 17 17 17 0 18 5 5 0 19 15 15 0 20 2 2 0 21 14 14 0 22 17 17 0 23 10 10 0 24 23 23 0 25 10 10 0 26 17 17 0 27 23 23 0 28 21 21 0 29 29 29 0 30 7 7 0 31 21 ...
output:
99999 99998 17156473 16956478 16856480 560562708 16756477 476680296 476280304 89674349 409354419 120115260 392397896 179441871 904069954 868517948 99983 725120619 306715524 63350995 241789649 240689576 759619845 15056494 355197471 389718349 171063700 124494310 99971 751483234 420705241 881548301 999...
result:
wrong answer 1st numbers differ - expected: '13', found: '99999'
Test #7:
score: 0
Wrong Answer
time: 241ms
memory: 22312kb
input:
7 4 100000 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 5 2 2 0 5 2 2 0 7 1 1 0 8 1 1 0 6 1 1 0 7 3 3 0 9 3 3 0 12 2 2 0 10 2 2 0 13 1 1 0 13 4 4 0 13 7 7 0 15 1 1 0 15 7 7 0 16 7 7 0 19 1 1 0 18 8 8 0 19 2 2 0 23 1 1 0 23 5 5 0 24 8 8 0 23 6 6 0 27 3 3 0 28 4 4 0 26 12 12 0 29 6 6 0 30 1 1 0 31 12 12 0 30 9 9 0...
output:
1 1 1 99996 3 99992 15756550 252088916 6 1 15556566 942775195 3 272800954 31513100 1 545601908 15156550 99996 15156550 99996 61566346 307831730 15556566 63026200 902329951 863619999 848463449 3 328289865 3 99992 252088916 13756606 883204338 728995645 260007145 902329951 15156550 752323173 260007145 ...
result:
wrong answer 4th numbers differ - expected: '21', found: '99996'
Test #8:
score: 0
Wrong Answer
time: 1ms
memory: 5564kb
input:
8 4 100000 1 1 1 0 2 2 2 0 3 2 2 1 4 2 2 2 5 3 3 0 6 6 6 2 7 1 1 6 8 8 8 2 9 1 1 6 10 2 2 3 11 4 4 2 12 6 6 5 13 2 2 11 14 1 1 6 15 7 7 4 16 7 7 3 17 14 14 15 18 12 12 12 19 17 17 3 20 20 20 11 21 5 5 7 22 12 12 3 23 14 14 10 24 3 3 1 25 23 23 10 26 5 5 18 27 5 5 25 28 18 18 1 29 2 2 14 30 23 23 3 3...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Test #9:
score: 0
Wrong Answer
time: 1ms
memory: 5516kb
input:
9 4 100000 1 1 1 0 1 1 1 0 1 1 1 0 3 1 1 0 4 2 2 1 6 2 2 2 6 1 1 2 8 3 3 2 9 1 1 4 8 4 4 0 9 4 4 0 12 6 6 3 13 3 3 4 13 6 6 3 15 5 5 0 15 2 2 7 15 4 4 2 17 5 5 2 18 5 5 0 18 4 4 6 19 2 2 8 22 8 8 9 23 3 3 10 24 6 6 12 25 7 7 13 24 1 1 11 27 3 3 7 27 12 12 2 28 4 4 0 30 3 3 9 31 15 15 15 32 1 1 7 31 ...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Test #10:
score: 0
Wrong Answer
time: 249ms
memory: 24456kb
input:
10 4 100000 1 1 1 0 2 1 1 0 3 3 3 0 4 3 4 0 5 3 5 0 6 1 4 0 7 5 5 0 8 5 7 0 9 3 6 0 10 6 10 0 11 1 2 0 12 8 11 0 13 4 12 0 14 2 12 0 15 7 10 0 16 6 8 0 17 13 15 0 18 8 9 0 19 2 6 0 20 8 14 0 21 3 18 0 22 11 18 0 23 5 11 0 24 6 12 0 25 3 24 0 26 13 23 0 27 3 8 0 28 14 22 0 29 4 26 0 30 1 5 0 31 13 17...
output:
99999 17256472 99997 17156470 611732126 279082508 560162712 576019212 627599917 34598759 33724427 963517246 879142257 215672115 691083805 710899085 774696069 389555460 433534025 633742383 546720793 131875681 389412610 756068338 917596981 198677184 690370145 270770212 845297519 395348729 525262117 43...
result:
wrong answer 1st numbers differ - expected: '16', found: '99999'
Test #11:
score: 0
Wrong Answer
time: 243ms
memory: 22900kb
input:
11 4 100000 1 1 1 0 2 1 2 0 3 1 2 0 3 1 2 0 5 3 4 0 5 1 3 0 5 2 3 0 8 1 3 0 9 2 5 0 10 3 5 0 11 4 6 0 10 1 3 0 11 6 8 0 13 4 8 0 13 2 7 0 14 1 3 0 17 3 8 0 17 5 7 0 19 10 11 0 19 1 2 0 20 5 12 0 22 12 12 0 22 8 10 0 23 6 14 0 23 2 8 0 25 2 9 0 27 6 9 0 26 9 15 0 29 3 10 0 30 9 9 0 30 12 13 0 32 14 1...
output:
99999 17356470 17456469 645945080 100000 663401549 593575673 699728222 457651831 404808225 258632870 261645413 454023906 258732870 417868569 828558734 822576795 990335260 15556470 820649641 59821870 15156493 941004622 835369044 472739799 462359460 681237419 626995696 913771527 908047812 388152212 44...
result:
wrong answer 1st numbers differ - expected: '37', found: '99999'
Test #12:
score: 0
Wrong Answer
time: 241ms
memory: 22148kb
input:
12 4 100000 1 1 1 0 2 1 2 0 3 2 3 0 4 1 3 0 2 1 1 0 4 2 2 0 3 1 2 0 8 1 4 0 8 1 3 0 5 2 5 0 9 1 4 0 10 3 5 0 11 1 6 0 11 3 6 0 11 3 3 0 14 2 6 0 17 3 7 0 14 2 4 0 14 4 6 0 18 2 8 0 18 6 9 0 21 8 10 0 22 5 5 0 20 6 8 0 22 1 4 0 24 3 9 0 26 3 8 0 25 3 3 0 24 6 7 0 25 5 9 0 27 2 9 0 32 4 6 0 32 9 11 0 ...
output:
99999 17256470 16656470 899491353 99999 17256470 86782345 208277630 208277628 865578402 312416444 17356470 645582034 34012940 16656470 820459475 19621134 783481872 306116451 540782288 253345482 17356470 457350341 138851760 483283191 50913939 272655809 645582034 766825402 609803993 644612632 95181738...
result:
wrong answer 1st numbers differ - expected: '69', found: '99999'
Test #13:
score: 0
Wrong Answer
time: 1ms
memory: 5860kb
input:
13 4 100000 1 1 1 0 2 1 2 1 3 1 2 2 4 1 3 2 5 1 5 4 6 1 4 4 7 6 6 1 8 3 7 5 9 3 4 4 10 5 6 2 11 6 9 4 12 5 11 9 13 1 3 4 14 6 10 10 15 4 6 8 16 3 8 6 17 1 9 3 18 3 13 8 19 3 11 10 20 2 4 11 21 12 13 0 22 13 17 20 23 9 17 1 24 10 11 16 25 22 25 9 26 5 9 4 27 12 27 26 28 13 13 22 29 8 23 1 30 21 23 19...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Test #14:
score: 0
Wrong Answer
time: 1ms
memory: 5656kb
input:
14 4 100000 1 1 1 0 1 1 1 0 1 1 1 0 4 1 2 1 1 1 1 0 5 1 1 2 6 1 1 0 6 2 2 1 5 2 3 2 5 1 2 1 7 2 2 1 8 1 2 1 11 2 4 1 11 4 4 2 15 2 4 0 13 1 3 3 15 1 3 3 18 2 4 4 16 2 5 5 16 4 4 0 18 6 6 4 22 4 4 5 18 2 5 5 20 5 6 5 24 1 6 4 25 5 6 2 22 3 4 1 28 3 7 0 25 2 4 4 29 1 6 4 27 3 8 0 28 5 5 7 30 2 3 1 33 ...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Test #15:
score: 0
Wrong Answer
time: 1ms
memory: 5644kb
input:
15 4 100000 1 1 1 0 1 1 1 0 2 1 2 0 1 1 1 0 4 1 3 1 3 2 2 1 5 1 2 0 5 2 2 1 7 2 3 1 9 1 2 0 9 2 3 0 8 1 2 1 9 1 2 0 10 3 3 2 11 2 3 1 13 2 3 3 15 3 5 4 14 4 4 2 16 2 4 0 20 4 5 5 18 1 6 4 21 2 5 6 19 4 5 4 23 3 7 4 23 3 5 0 25 3 3 8 26 4 8 8 26 3 7 6 28 6 9 5 26 6 9 2 29 8 9 7 29 6 10 1 31 4 4 5 34 ...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Test #16:
score: 0
Wrong Answer
time: 1ms
memory: 5860kb
input:
16 4 100000 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 5 2 2 1 5 1 1 0 5 1 2 1 4 1 2 0 7 1 2 2 6 1 2 0 7 2 3 0 12 1 4 0 11 1 1 2 13 1 4 0 14 3 3 4 12 1 4 0 16 2 2 1 18 1 7 5 19 6 6 5 20 4 5 1 17 2 5 4 22 1 3 4 23 1 3 3 21 5 5 9 22 3 4 3 24 1 7 3 23 2 5 1 27 2 5 4 25 2 8 7 29 6 7 3 27 5 9 6 30 10 11 6 30 1 2 3 ...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Test #17:
score: 0
Wrong Answer
time: 1ms
memory: 5636kb
input:
17 4 100000 1 1 1 0 1 1 1 0 1 1 1 0 2 1 1 0 2 1 2 1 4 1 1 0 3 1 2 1 7 2 3 0 8 3 3 0 6 1 3 0 9 2 3 0 8 1 3 1 9 3 4 2 11 3 4 3 13 2 3 0 12 4 5 4 16 1 2 1 15 1 2 2 19 2 5 5 16 3 5 4 19 1 4 5 21 3 4 5 23 3 5 0 21 1 6 1 23 3 3 2 25 1 2 2 26 1 3 0 26 5 6 6 27 2 4 3 28 1 5 8 31 2 3 5 29 3 7 1 32 7 10 10 32...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Test #18:
score: 0
Wrong Answer
time: 1ms
memory: 5828kb
input:
18 4 100000 1 1 1 0 1 1 1 0 3 1 2 1 2 1 2 0 2 2 2 0 5 1 3 1 6 1 1 1 6 2 3 2 6 1 3 2 9 1 4 1 10 2 3 1 12 1 3 0 10 1 4 2 11 2 5 0 12 4 5 1 14 2 4 1 15 5 6 2 16 4 5 5 18 3 3 5 18 1 6 4 18 3 4 4 21 2 4 3 21 4 7 4 23 7 9 3 23 1 5 3 25 3 5 3 26 5 6 2 25 1 7 4 29 3 4 6 30 4 11 2 29 1 3 3 29 1 5 6 32 9 12 0...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Test #19:
score: 0
Wrong Answer
time: 1ms
memory: 5572kb
input:
19 4 100000 1 1 1 0 1 1 1 0 1 1 1 0 2 1 2 1 2 2 2 0 3 1 1 1 4 1 1 0 8 1 3 0 7 2 2 0 8 2 2 2 8 1 1 1 11 2 4 3 13 1 3 2 13 1 3 1 12 1 2 0 15 2 5 1 16 4 5 0 18 4 5 3 17 2 4 0 19 3 6 5 21 4 8 2 21 2 6 4 23 7 8 6 22 1 4 3 22 1 3 2 24 1 8 1 25 5 5 1 26 3 3 2 26 1 10 5 30 8 9 0 29 3 5 2 29 3 6 0 31 4 7 10 ...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
Test #20:
score: 0
Wrong Answer
time: 1ms
memory: 5632kb
input:
20 4 100000 1 1 1 0 1 1 1 0 1 1 1 0 3 1 2 1 5 1 1 0 4 1 2 1 5 1 1 2 8 4 4 0 8 1 2 3 10 3 4 0 11 5 5 3 10 3 4 2 11 2 3 3 12 1 7 6 14 1 2 1 15 5 8 3 15 1 2 6 17 5 8 4 17 3 4 0 18 7 9 6 20 1 10 2 21 1 4 9 22 1 9 9 23 3 8 6 25 3 7 8 24 2 7 6 27 1 9 8 27 12 12 8 29 3 11 3 30 2 6 4 31 6 14 8 30 6 8 3 33 8...
output:
result:
wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements