QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #504119 | #9159. 登山 | yizhiming | 15 | 12ms | 17948kb | C++14 | 7.4kb | 2024-08-04 07:39:04 | 2024-08-04 07:39:09 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define int long long
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int N = 1e5+5;
const int Mod = 998244353;
int n;
struct bb{
int id,k;
}sta[N*20],st[N*20];
int tp,tt,Ct;
struct seg{
struct aa{
int lc,rc,cnt,sum,val,tag,rev;//节点个数，总和，区间权值和，区间加和标记，清空标记
void clear(){
lc = rc = cnt = sum = val = tag = rev = 0;
}
}node[N*2];
int tot;
int newnode(){
int u = ++tot;
node[u].clear();
return u;
}
void build(int &u,int l,int r){
u = newnode();
if(l==r){
return;
}
int mid = (l+r)/2;
build(node[u].lc,l,mid);
build(node[u].rc,mid+1,r);
}
void pushup(int u){
node[u].cnt = node[node[u].lc].cnt+node[node[u].rc].cnt;
node[u].sum = (node[node[u].lc].sum+node[node[u].rc].sum)%Mod;
node[u].val = (node[node[u].lc].val+node[node[u].rc].val)%Mod;
}
void lazy_rev(int u){
node[u].sum = node[u].cnt = 0;
node[u].rev = 1;node[u].tag = 0;
}
void lazy_tag(int u,int x,int l,int r){
node[u].tag+=x;
node[u].cnt+=(r-l+1)*x;
node[u].sum+=x*node[u].val%Mod;
node[u].sum+=Mod;
node[u].sum%=Mod;
}
void pushdown(int u,int l,int r){
if(node[u].rev){
lazy_rev(node[u].lc);
lazy_rev(node[u].rc);
node[u].rev = 0;
}
if(node[u].tag){
int mid = (l+r)/2;
lazy_tag(node[u].lc,node[u].tag,l,mid);
lazy_tag(node[u].rc,node[u].tag,mid+1,r);
node[u].tag = 0;
}
}
void upd(int u,int l,int r,int ll,int rr,int x){
if(ll>rr||!ll||!rr){
return;
}
// cout<<"LR:"<<u<<" "<<l<<" "<<r<<" "<<node[u].cnt<<" "<<node[u].sum<<" "<<node[u].tag<<"\n";
if(l==ll&&r==rr){
lazy_tag(u,x,l,r);
// cout<<"NOW:"<<u<<" "<<node[u].tag<<" "<<node[u].rev<<"\n";
return;
}
pushdown(u,l,r);
int mid = (l+r)/2;
if(rr<=mid){
upd(node[u].lc,l,mid,ll,rr,x);
}else if(ll>mid){
upd(node[u].rc,mid+1,r,ll,rr,x);
}else{
upd(node[u].lc,l,mid,ll,mid,x);
upd(node[u].rc,mid+1,r,mid+1,rr,x);
}
pushup(u);
// cout<<"LR:"<<u<<" "<<l<<" "<<r<<" "<<node[u].sum<<"\n";
}
void add(int u,int l,int r,int x,int y){
if(l==r){
node[u].val+=y;node[u].val = (node[u].val+Mod)%Mod;
node[u].sum+=y*node[u].cnt%Mod;
node[u].sum+=Mod;
node[u].sum%=Mod;
return;
}
pushdown(u,l,r);
int mid = (l+r)/2;
if(x<=mid){
add(node[u].lc,l,mid,x,y);
}else{
add(node[u].rc,mid+1,r,x,y);
}
pushup(u);
}
void ask(int u,int l,int r,int ll,int rr){
if(!node[u].cnt){
return;
}
if(l==r){
sta[++tp] = (bb){node[u].cnt,l};
Ct+=node[u].cnt;
node[u].cnt = 0;node[u].tag = 0;node[u].sum = 0;
return;
}
pushdown(u,l,r);
int mid = (l+r)/2;
if(rr<=mid){
ask(node[u].lc,l,mid,ll,rr);
}else if(ll>mid){
ask(node[u].rc,mid+1,r,ll,rr);
}else{
ask(node[u].lc,l,mid,ll,mid);
ask(node[u].rc,mid+1,r,mid+1,rr);
}
pushup(u);
}
int qry(int u,int l,int r,int ll,int rr){
if(ll>rr){
return 0;
}
if(l==ll&&r==rr){
return node[u].sum;
}
pushdown(u,l,r);
int mid = (l+r)/2;
if(rr<=mid){
return qry(node[u].lc,l,mid,ll,rr);
}else if(ll>mid){
return qry(node[u].rc,mid+1,r,ll,rr);
}else{
return (qry(node[u].lc,l,mid,ll,mid)+qry(node[u].rc,mid+1,r,mid+1,rr))%Mod;
}
}
int tmp[N];
void find(int u,int l,int r){
if(l==r){
tmp[l] = node[u].cnt;
return;
}
pushdown(u,l,r);
int mid = (l+r)/2;
find(node[u].lc,l,mid);
find(node[u].rc,mid+1,r);
pushup(u);
}
void print(int u){
find(u,1,n);
for(int i=1;i<=n;i++){
cout<<tmp[i]<<" ";
}
cout<<"\n";
cout<<"---------------\n";
}
}T;
int fa[N],l[N],r[N],h[N];
int top[N],bot[N],dep[N],siz[N],son[N],rt;
vector<int>ed[N];
void dfs1(int u){
siz[u] = 1;son[u] = 0;dep[u] = dep[fa[u]]+1;
for(auto x:ed[u]){
dfs1(x);
siz[u]+=siz[x];
if(siz[x]>siz[son[u]]){
son[u] = x;
}
}
}
void dfs2(int u,int t){
top[u] = t;
bot[t] = u;
if(!son[u]){
return;
}
dfs2(son[u],t);
for(auto x:ed[u]){
if(x==son[u]){
continue;
}
dfs2(x,x);
}
}
int rk[N],f[N];
void sol(int u,int v,bool op){
v = min(v,dep[u]-h[u]-1);
st[++tt] = (bb){1,min(v,dep[u]-l[u])};
st[++tt] = (bb){-1,min(v,dep[u]-r[u]-1)};
// cout<<"LR:"<<u<<" "<<min(v,dep[u]-r[u]-1)<<" "<<min(v,dep[u]-l[u])<<" "<<dep[u]<<" "<<r[u]<<"\n";
for(auto x:ed[u]){
if(x==son[u]&&op){
continue;
}
sol(x,v,op);
}
}
void work(int t,int u){
// int U = u;
// tp = 0;
// while(1){
// tt = 0;
// sol(u,1e9,1);
// for(int i=1;i<=tt;i++){
// auto x = st[i];
// T.upd(rt,1,n,x.k,x.k,x.id);
// }
// Ct = 0;
// T.ask(rt,1,n,dep[u]-h[u],n);
// rk[u] = tp;
// T.upd(rt,1,n,dep[u]-h[u]-1,dep[u]-h[u]-1,Ct);
// if(u==t){
// break;
// }
// u = fa[u];
// }
// T.lazy_rev(rt);
// u = U;
while(1){
tt = 0;sol(t,1e9,0);
for(int i=1;i<=tt;i++){
auto x = st[i];
T.upd(rt,1,n,1,x.k,x.id);
}
f[t] = T.qry(rt,1,n,1,n);
if(t==1){
f[t] = 1;
}
T.add(rt,1,n,dep[t],f[t]);
T.lazy_rev(rt);
if(t==u){
break;
}
t = son[t];
}
// tt = 0;
// sol(t,1e9,0);
// for(int i=1;i<=tt;i++){
// auto x = st[i];
// T.upd(rt,1,n,1,x.k,x.id);
// }
// while(1){
// f[t] = T.qry(rt,1,n,1,n);
// if(t==1){
// f[t] = 1;
// }
// T.add(rt,1,n,dep[t],f[t]);
// tt = 0;sol(t,1e9,1);
// for(int i=1;i<=tt;i++){
// auto x = st[i];
// T.upd(rt,1,n,1,x.k,-x.id);
// }
// for(int i=rk[t];i>rk[son[t]];i--){
// auto x = sta[i];
// T.upd(rt,1,n,1,dep[t]-h[t]-1,-x.id);
// T.upd(rt,1,n,1,x.k,x.id);
// }
// if(t==u){
// break;
// }
// t = son[t];
// }
// T.lazy_rev(rt);
}
void init(int u){
// if(u==1){
// top[son[u]] = son[u];
// int U = son[u];
// while(son[U]){
// U = son[U];top[U] = son[u];
// }
// T.add(rt,1,n,1,1);
// for(auto x:ed[u]){
// init(x);
// }
// return;
// }
if(son[u]){
init(son[u]);
}else{
work(top[u],u);
}
for(auto x:ed[u]){
if(x!=son[u]){
init(x);
}
}
T.add(rt,1,n,dep[u],-f[u]);
}
void init(){
n = read();
ed[1].clear();T.tot = 0;rt = 0;
for(int i=2;i<=n;i++){
fa[i] = read();
l[i] = read();r[i] = read();h[i] = read();
ed[i].clear();
}
for(int i=2;i<=n;i++){
ed[fa[i]].push_back(i);
}
dfs1(1);dfs2(1,1);
T.build(rt,1,n);
init(1);
for(int i=2;i<=n;i++){
cout<<f[i];
if(i!=n){
cout<<" ";
}
}
cout<<"\n";
// cout<<"TOP:"<<top[7]<<" "<<top[10]<<" "<<top[13]<<" "<<top[14]<<" "<<top[15]<<" "<<son[1]<<"\n";
}
int c,TT;
signed main(){
// freopen("ex_2.in","r",stdin);
// freopen("me.txt","w",stdout);
c = read();TT = read();
while(TT--){
init();
}
return 0;
}
/*
首先把贡献转换成对于每个点，枚举其子树内的所有点
根据枚举的点和路径上的权值得到一个合法的区间的贡献
区间对应当前点的一段区间的祖先贡献
对所有的区间求和即可
然后注意到我们直接树剖的话链是从下往上的
但是由于需要知道祖先贡献
所有我们需要从上往下，怎么办呢？直接从下往上做一遍，然后倒着撤销做一遍即可
要注意到的细节就是撤销的复杂度均摊下来是对的
*/
Details
Tip: Click on the bar to expand more detailed information
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 13808kb
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: 7ms
memory: 13820kb
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: 12ms
memory: 15940kb
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: 0
Time Limit Exceeded
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:
Pretest #5:
score: 0
Time Limit Exceeded
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:
Pretest #6:
score: 0
Time Limit Exceeded
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:
result:
Pretest #7:
score: 0
Time Limit Exceeded
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:
result:
Pretest #8:
score: 0
Time Limit Exceeded
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:
Pretest #9:
score: 0
Time Limit Exceeded
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:
Pretest #10:
score: 0
Time Limit Exceeded
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:
result:
Pretest #11:
score: 0
Time Limit Exceeded
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:
result:
Pretest #12:
score: 0
Time Limit Exceeded
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:
result:
Pretest #13:
score: 0
Time Limit Exceeded
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:
Pretest #14:
score: 0
Time Limit Exceeded
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:
Pretest #15:
score: 0
Time Limit Exceeded
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:
Pretest #16:
score: 0
Time Limit Exceeded
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:
Pretest #17:
score: 0
Time Limit Exceeded
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:
Pretest #18:
score: 0
Time Limit Exceeded
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:
Pretest #19:
score: 0
Time Limit Exceeded
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:
Pretest #20:
score: 0
Time Limit Exceeded
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:
Final Tests
Test #1:
score: 5
Accepted
time: 3ms
memory: 17948kb
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: 8ms
memory: 13884kb
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: 8ms
memory: 13852kb
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: 0
Time Limit Exceeded
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:
Test #5:
score: 0
Time Limit Exceeded
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:
Test #6:
score: 0
Time Limit Exceeded
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:
result:
Test #7:
score: 0
Time Limit Exceeded
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:
result:
Test #8:
score: 0
Time Limit Exceeded
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:
Test #9:
score: 0
Time Limit Exceeded
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:
Test #10:
score: 0
Time Limit Exceeded
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:
result:
Test #11:
score: 0
Time Limit Exceeded
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:
result:
Test #12:
score: 0
Time Limit Exceeded
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:
result:
Test #13:
score: 0
Time Limit Exceeded
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:
Test #14:
score: 0
Time Limit Exceeded
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:
Test #15:
score: 0
Time Limit Exceeded
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:
Test #16:
score: 0
Time Limit Exceeded
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:
Test #17:
score: 0
Time Limit Exceeded
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:
Test #18:
score: 0
Time Limit Exceeded
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:
Test #19:
score: 0
Time Limit Exceeded
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:
Test #20:
score: 0
Time Limit Exceeded
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...