QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#644728 | #7626. Quake and Rebuild | Displace_ | TL | 2530ms | 6624kb | C++14 | 2.8kb | 2024-10-16 15:17:23 | 2024-10-16 15:17:23 |
Judging History
answer
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
#define ep emplace_back
template <typename T>inline void read(T &x){
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
const int N=2e5+5;
const int B=600;
int n, m;
int lp[B], rp[B], bid[N];
int fa[N], nxt[N], dis[N];
int dt[B];
inline void rebuild(int i){
if(dt[i]>=B) return ;
for(int j=lp[i]; j<=rp[i]; ++j){
int x=j; dis[j]=0;
while(x>=lp[i]) ++dis[j], x=max(1, fa[x]-dt[i]);
nxt[j]=x;
}
}
#define gf(x) (dt[bid[x]]<B?nxt[x]:max(1, fa[x]-dt[bid[x]]))
inline int lca(int x, int y){
while(gf(x)^gf(y)){
if(x<y) y=gf(y);
else x=gf(x);
}
if(bid[x]!=bid[y]) return gf(x);
while(x^y){
if(x<y) y=max(1, fa[y]-dt[bid[y]]);
else x=max(1, fa[x]-dt[bid[x]]);
}
return x;
}
inline int dep(int x){
int ret=0;
while(x^1){
if(dt[bid[x]]<B) ret+=dis[x], x=nxt[x];
else ++ret, x=max(1, fa[x]-dt[bid[x]]);
}
return ret;
}
inline int getd(int x, int y){
if(x==y) return 0;
return dep(x)+dep(y)-2*dep(lca(x, y));
}
inline int jump(int x, int t){
while(gf(x)>t) x=gf(x);
while(max(1, fa[x]-dt[bid[x]])>t) x=max(1, fa[x]-dt[bid[x]]);
return x;
}
inline bool cmp(int x, int y){
if(x==y) return false;
int t=lca(x, y);
if(t==x) return true;
if(t==y) return false;
return jump(x, t)<jump(y, t);
}
int main(){
// freopen("D:\\nya\\acm\\B\\test.in","r",stdin);
// freopen("D:\\nya\\acm\\B\\test.out","w",stdout);
read(n); read(m);
for(int i=2; i<=n; ++i) read(fa[i]);
for(int i=2; i<=n; ++i) bid[i]=(i-2)/B+1;
bid[1]=0;
lp[0]=rp[0]=1; dt[0]=B;
for(int i=1; i<=bid[n]; ++i) lp[i]=rp[i-1]+1, rp[i]=rp[i-1]+B;
rp[bid[n]]=n;
for(int i=1; i<=bid[n]; ++i) rebuild(i);
while(m--){
int op; read(op);
if(op==1){
int l, r, d; read(l); read(r); read(d);
if(bid[l]==bid[r]){
for(int i=l; i<=r; ++i) fa[i]-=d;
rebuild(bid[l]);
continue;
}
for(int i=l; i<=rp[bid[l]]; ++i) fa[i]-=d;
rebuild(bid[l]);
for(int i=lp[bid[r]]; i<=r; ++i) fa[i]-=d;
rebuild(bid[r]);
for(int i=bid[l]+1; i<bid[r]; ++i){
dt[i]+=d; dt[i]=min(dt[i], n); rebuild(i);
}
}
else{
int k, x; vector<int> vec;
read(k);
if(k==0){
printf("0\n");
continue;
}
while(k--){
read(x); vec.ep(x);
}
sort(vec.begin(), vec.end(), cmp);
vec.ep(vec[0]);
int ans=0;
for(int i=1; i<(int)vec.size(); ++i) ans+=getd(vec[i-1], vec[i]);
ans>>=1;
printf("%d\n", ans+1);
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4028kb
input:
4 5 1 2 2 2 2 1 4 1 2 3 1 2 3 2 3 4 1 4 4 1 2 2 3 4
output:
3 4 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5904kb
input:
10 10 1 2 3 3 4 5 7 7 9 1 2 10 3 2 9 9 5 3 10 7 2 4 6 8 1 6 10 3 1 2 7 3 1 7 10 3 2 2 4 3 2 3 7 4 4 1 3 9 3 1 3 9 3 1 10 10 3
output:
10 3 3
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 138ms
memory: 5872kb
input:
3051 198219 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 4 1 1 1 6 3 1 1 2 2 2 1 6 3 7 3 3 5 1 2 7 2 5 1 3 4 1 6 2 1 2 1 10 3 3 1 3 2 2 6 3 9 3 1 12 5 1 5 6 7 7 3 2 6 5 8 12 3 7 16 3 9 4 7 1 2 13 3 3 5 9 9 9 6 5 4 41 8 7 10 7 2 7 2 4 14 4 3 1 16 2 6 3 10 3 4 9 10 1 6 1 14 6 10 8 9 6 3 1 1 1 13 22 4 20 17 1 15 ...
output:
78 78 70 64 60 55 60 58 52 54 51 53 56 51 51 57 55 52 49 55 49 50 53 49 49 48 49 48 53 50 50 54 47 52 45 49 49 46 47 48 49 50 48 49 47 48 47 49 48 50 48 49 48 47 49 48 51 48 48 45 45 46 50 50 50 48 49 46 47 47 46 48 48 47 49 47 46 47 46 47 46 45 47 49 49 50 51 48 48 49 47 47 48 50 46 47 48 50 46 47 ...
result:
ok 13214 lines
Test #4:
score: 0
Accepted
time: 169ms
memory: 3920kb
input:
6173 198631 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...
output:
2819 1049 1155 831 722 5962 123 624 554 601 241 597 81 29 34 390 350 443 385 6038 6083 258 5 315 27 281 6029 300 6136 322 227 46 271 263 26 268 257 6101 5816 255 258 156 243 270 186 6099 16 13 5435 163 7 35 219 182 214 10 24 23 194 178 188 183 200 167 158 197 24 189 131 35 167 24 189 15 183 176 6050...
result:
ok 30261 lines
Test #5:
score: 0
Accepted
time: 79ms
memory: 4016kb
input:
9724 198809 1 1 1 1 1 1 1 1 1 4 2 2 1 2 1 4 1 5 1 3 4 2 2 4 2 7 4 1 2 6 9 2 1 1 2 3 1 1 3 4 3 1 2 1 18 1 3 4 2 4 4 6 1 4 2 1 7 11 4 1 5 6 2 12 3 4 4 7 1 1 11 4 15 21 3 4 15 1 1 12 11 3 1 1 16 9 14 2 5 9 3 5 9 3 8 5 15 16 9 14 13 8 2 4 5 10 6 1 10 11 10 12 7 4 36 6 5 7 6 13 7 1 14 5 1 6 8 7 1 10 20 6...
output:
24 25 31 31 27 25 29 23 23 21 26 23 21 24 23 23 26 26 21 24 27 23 23 23 20 19 20 18 28 25 26 21 19 21 21 26 20 23 17 20 18 21 22 22 18 21 25 18 17 18 24 18 16 18 19 24 20 18 19 17 17 21 25 19 21 23 19 23 15 17 19 19 22 18 20 18 21 19 18 18 15 16 22 17 17 18 13 16 19 16 15 16 18 16 15 17 15 18 18 20 ...
result:
ok 66269 lines
Test #6:
score: 0
Accepted
time: 531ms
memory: 6396kb
input:
12796 185791 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...
output:
12100 7532 12357 12774 211 12761 5309 1646 12726 1882 247 118 1660 12229 12143 1499 1368 1273 1387 341 274 1374 1237 1359 112 1152 981 12681 949 890 820 774 62 644 836 925 12 13 1203 666 732 731 1127 12320 11473 82 655 12788 569 5866 621 2798 12114 85 609 11827 1 12455 56 605 575 530 54 645 1845 93 ...
result:
ok 3210 lines
Test #7:
score: 0
Accepted
time: 166ms
memory: 5856kb
input:
16122 194030 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...
output:
9730 7096 4371 4171 3732 3716 3273 2910 2530 2423 2366 2351 2013 2196 2430 1891 1833 1852 1638 1709 1762 1699 1423 1295 1471 1255 1356 1428 1214 1191 1066 1104 1131 1116 1010 860 964 949 927 994 879 829 718 787 786 754 757 795 820 739 761 689 659 658 587 663 654 658 631 593 633 583 575 598 554 579 4...
result:
ok 9701 lines
Test #8:
score: 0
Accepted
time: 144ms
memory: 6080kb
input:
19492 191214 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3 1 2 10 10 1 2 2 1 1 1 1 2 1 2 2 4 3 1 1 4 10 2 5 6 1 1 6 11 3 7 1 6 5 4 8 8 12 2 4 5 6 1 2 4 10 4 8 15 3 1 15 1 1 4 9 6 9 2 2 11 3 6 11 17 6 6 2 5 10 8 3 3 4 2 1 3 3 12 1 14 1 1 6 1 5 7 23 7 12 8 13 1 11 13 6 22 3 20 2 8 4 1 41 5 3 27 13 15 4 4 6 9 ...
output:
207 284 264 237 41 207 17559 198 186 201 168 1 1461 9 218 170 156 191 7 195 189 177 165 18623 170 25 151 18433 168 181 164 179 188 18572 1 171 172 182 137 179 184 127 162 166 167 171 17 147 180 165 175 173 167 1359 20 161 138 175 169 176 178 6 152 178 7 121 16 12 4 9 8 5 4 6 29 6 7 10 42 5 3 1 5 27 ...
result:
ok 18556 lines
Test #9:
score: 0
Accepted
time: 87ms
memory: 4128kb
input:
22808 195820 1 1 1 1 1 1 1 1 1 1 2 2 1 1 2 2 1 1 3 2 1 2 4 4 1 2 1 5 4 1 4 2 1 3 1 1 3 1 4 3 4 5 15 1 6 10 1 1 3 1 1 1 1 3 5 7 4 2 3 15 4 4 1 11 1 2 5 2 2 12 4 3 1 9 6 4 2 1 3 5 5 1 4 1 2 16 15 1 6 1 10 1 9 6 9 2 1 12 6 2 13 2 3 1 8 17 2 8 1 16 5 28 4 24 2 9 5 1 11 18 15 6 7 10 3 1 1 11 8 1 12 4 7 1...
output:
42 45 42 45 40 47 43 37 38 41 37 44 42 38 42 34 34 32 37 37 37 39 35 45 35 40 32 36 43 34 33 39 29 32 33 33 33 31 28 32 35 31 23 33 31 30 26 34 28 30 35 32 32 30 33 28 26 29 30 26 24 27 25 28 22 30 26 27 23 29 31 25 27 30 26 26 33 30 27 26 21 32 27 28 28 25 31 26 24 24 24 23 30 22 26 21 26 27 24 22 ...
result:
ok 39164 lines
Test #10:
score: 0
Accepted
time: 170ms
memory: 4468kb
input:
26352 183295 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 2 1 1 1 1 1 2 2 1 1 1 2 11 1 2 1 4 1 2 3 1 3 3 4 2 3 2 5 3 2 1 2 1 3 6 1 2 3 1 6 3 2 4 3 1 7 3 6 3 10 1 1 2 5 1 1 7 3 2 3 3 8 7 2 5 9 2 3 1 9 3 1 2 8 7 5 1 2 1 1 11 5 2 3 8 3 7 4 1 6 5 1 10 16 11 3 4 3 6 14 4 3 15 27 14 2 3 5 6 14 15 11 21 2 3 2 1...
output:
25212 25 316 497 330 4 314 304 24633 297 285 5 252 26284 11 256 281 275 26265 12 1 14 17 12 6 12 5 10 3 15 9 7 10 1 1 9 9 3 40 11 10 19 9 9 9 14 4 17 3 8 13 5 6 9 32 12 6 4 6 3 4 4 1 4 1991 29 40 1 5 30 911 3 9 11 44 45 3 1 15 1 16 9 16 14 3 15 31 15 1 7 14 367 3479 5 4 14 6 25 13 4 7 3 5 14 18 8 13...
result:
ok 3811 lines
Test #11:
score: 0
Accepted
time: 100ms
memory: 4196kb
input:
27196 199560 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 3 2 4 1 1 2 4 1 2 1 2 5 3 5 4 1 1 2 4 1 2 11 4 2 7 1 1 3 1 1 2 2 5 2 2 6 1 3 3 2 4 7 2 5 3 2 6 10 4 2 6 3 2 1 2 2 17 1 1 2 5 9 5 4 19 12 2 12 3 2 19 4 4 12 7 6 5 9 3 2 6 3 13 1 1 11 9 6 14 9 3 3 4 17 6 1 5 13 3 1 32 15 26 3 1 2 15 3 1 4 14 2 7 2 1...
output:
82 78 77 73 75 72 69 68 65 65 63 59 65 60 65 71 58 67 64 64 62 61 62 67 46 61 54 60 56 55 51 52 45 47 54 51 49 45 53 45 53 46 43 41 42 51 48 48 43 40 44 45 42 47 43 40 42 51 44 44 42 44 43 39 43 42 40 41 44 41 39 41 39 42 36 41 42 38 42 38 42 42 44 40 44 45 35 37 38 38 40 37 38 42 42 41 35 40 39 37 ...
result:
ok 19956 lines
Test #12:
score: 0
Accepted
time: 931ms
memory: 4632kb
input:
32698 192710 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...
output:
32631 1529 1 1074 3158 151 32359 5093 4935 1295 32642 3805 365 3196 3342 2990 3159 3152 30578 509 2975 3034 32641 2753 7381 8616 2802 2351 32349 358 101 385 1998 8785 1 1959 5152 1923 1899 1763 395 1800 31873 1708 1729 185 1678 1507 1740 1591 1498 1633 102 1461 32109 1355 591 32295 1441 32692 146 53...
result:
ok 246 lines
Test #13:
score: 0
Accepted
time: 100ms
memory: 6232kb
input:
35920 186806 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 4 1 4 3 2 1 1 4 3 2 5 2 1 2 2 3 8 5 1 1 9 1 6 8 1 3 4 4 8 2 8 4 11 4 4 3 1 15 8 3 9 8 1 2 3 4 4 4 2 3 3 1 3 1 6 11 8 3 9 4 4 11 13 6 2 2 10 9 10 1 1 1 15 4 1 7 5 5 2 8 20 16 2 15 1 8 5 2 6 4 3 13 11 3 3 4 1 16 1 2 7 2 4 18 12 3 4 4 37 7 12 21 2 27 15 ...
output:
109 105 104 101 102 97 103 99 93 96 99 100 88 87 90 90 84 88 96 78 95 85 88 86 91 86 77 87 80 88 80 75 76 81 73 76 82 81 81 76 78 72 82 72 80 66 66 75 68 61 81 75 69 72 74 66 71 60 60 70 59 71 67 59 69 60 54 67 57 60 59 64 68 69 58 56 60 52 58 66 56 62 63 56 56 62 56 62 52 58 58 51 49 62 51 58 54 53...
result:
ok 15567 lines
Test #14:
score: 0
Accepted
time: 286ms
memory: 4520kb
input:
39372 196317 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 3 1 3 2 2 1 1 1 4 4 3 6 1 2 1 5 4 7 2 5 1 2 2 5 2 12 2 7 7 2 5 6 14 2 5 4 6 2 8 14 2 3 4 8 12 1 2 5 3 1 10 6 8 3 4 4 8 13 2 2 6 14 12 4 3 29 8 2 1 39 2 15 9 17 1 7 18 1 5 2 9 6 7 1 6 10 3 14 10 35 12 4 17 2 2 3 11 6 7 2 6 12 12 9 9 6 4 22 5 7 5 26 5 5...
output:
36323 444 26954 457 83 38918 85 36668 383 362 1535 35763 51 339 301 38085 49 327 291 269 34799 278 34 11 31977 297 297 261 288 38187 42 286 37406 11131 293 1495 288 38036 268 8 627 235 3191 245 232 37103 272 264 23 34 271 2433 242 269 86 263 5 239 214 4 241 230 233 34576 237 34789 260 232 36453 3710...
result:
ok 76 lines
Test #15:
score: 0
Accepted
time: 79ms
memory: 5940kb
input:
32241 199734 1 1 1 1 2 2 2 1 1 2 1 1 1 3 2 2 1 1 2 1 1 2 1 3 2 1 1 4 1 1 6 3 1 1 1 6 1 9 7 5 2 1 7 2 4 1 1 5 5 3 3 5 5 5 1 1 1 2 2 2 2 9 7 3 7 7 10 3 6 4 4 3 2 4 5 1 3 1 4 6 1 15 1 1 1 2 17 8 12 3 2 3 6 9 7 5 1 3 12 17 2 5 15 2 3 3 12 7 4 35 8 9 5 4 18 5 10 8 26 13 2 2 1 15 6 2 3 1 19 2 8 8 3 11 13 ...
output:
34 31 29 34 26 32 28 24 31 31 32 30 29 28 26 29 27 24 26 28 32 30 31 23 28 28 25 32 22 23 27 28 29 29 31 29 27 27 31 26 32 26 27 28 28 28 24 23 29 25 21 22 22 26 27 24 25 27 23 22 26 22 21 23 26 23 23 24 22 19 28 22 25 19 23 20 27 24 24 22 24 26 21 21 23 23 20 25 21 27 21 21 26 22 22 21 22 23 24 29 ...
result:
ok 66578 lines
Test #16:
score: 0
Accepted
time: 207ms
memory: 5092kb
input:
44885 197554 1 1 1 1 1 1 1 1 1 1 1 3 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 6 1 5 7 3 4 3 3 2 4 2 2 2 3 2 4 2 1 2 1 2 1 10 2 1 17 1 4 1 9 1 19 2 14 4 2 3 8 3 2 3 2 2 6 1 1 6 13 8 4 2 7 13 1 19 1 21 9 6 3 2 1 5 5 1 6 1 1 4 14 2 18 5 11 3 6 5 2 6 2 2 19 9 8 14 2 5 9 18 11 10 1 6 7 12 8 14 7 6 20 1 1 4 14...
output:
128 476 30 93 44813 104 463 420 421 422 7 399 430 369 404 5669 407 6 23 373 394 5 43609 363 379 31 375 9 319 1 342 350 285 16 31 357 330 321 338 309 316 30 71 327 335 69 227 300 33 334 330 323 333 26 50 50 285 6 14 302 5 1 25 7 285 35 310 19 23 256 10 41447 274 326 260 317 311 22 304 12 319 35 283 3...
result:
ok 507 lines
Test #17:
score: 0
Accepted
time: 92ms
memory: 4512kb
input:
47487 188796 1 1 1 1 1 1 1 1 2 1 2 2 2 2 1 1 1 3 2 3 2 2 2 1 2 8 4 2 4 1 1 7 6 3 3 6 5 2 1 1 1 8 5 1 2 3 7 1 3 5 4 6 1 7 6 4 7 5 4 7 9 10 7 7 10 6 7 6 24 1 4 3 11 7 1 7 3 1 1 2 4 10 5 6 16 3 18 3 6 3 4 2 1 3 10 22 11 14 8 8 3 28 3 5 5 6 4 27 4 1 5 3 14 15 15 20 27 5 7 25 2 25 6 2 5 2 14 16 2 5 20 11...
output:
12 13 13 12 12 13 12 13 14 13 13 11 12 11 12 12 13 15 14 14 12 11 13 13 13 11 10 13 12 13 10 10 12 11 13 12 14 11 10 11 14 10 11 14 10 8 13 11 12 10 12 13 13 13 13 12 12 11 14 12 14 13 10 12 12 13 13 11 14 13 11 12 9 11 12 13 10 10 11 11 11 11 12 12 11 11 13 11 11 12 12 12 13 13 14 11 12 10 11 11 11...
result:
ok 188796 lines
Test #18:
score: 0
Accepted
time: 216ms
memory: 4976kb
input:
50332 196622 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 2 3 1 5 3 1 3 1 1 2 6 2 1 2 2 6 1 1 2 1 2 2 2 1 2 3 6 4 2 3 1 1 1 1 1 1 3 10 3 6 7 3 4 12 2 4 17 2 9 14 7 1 5 5 1 3 1 2 1 5 8 3 3 2 1 1 7 3 2 1 20 1 3 5 1 9 5 7 1 1 1 26 20 16 5 7 9 3 1 13 8 4 4 26 8 4 5 1 2 5 1 1 6 21 7 4 1 12 9 6 8 6 11 4 12 4...
output:
519 482 447 482 405 21 5 412 19 393 5 396 46280 406 356 377 11 353 323 389 334 367 373 324 360 355 34 6 336 5 1 349 349 329 331 290 353 11 344 59 315 50161 330 336 296 318 314 320 306 321 9 19 12 324 318 5 329 9 293 4 291 332 4 303 6 4 309 304 320 16 13 289 305 301 324 311 12 300 311 296 1 278 44 23...
result:
ok 604 lines
Test #19:
score: 0
Accepted
time: 80ms
memory: 4700kb
input:
56089 161372 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 2 1 1 3 1 2 1 4 2 2 1 3 2 2 1 2 2 2 2 1 2 1 3 1 2 7 5 2 6 2 1 7 3 2 1 2 4 3 4 7 5 3 1 1 1 7 2 3 3 5 1 4 1 2 1 3 2 7 1 1 5 3 2 1 6 2 2 3 4 1 8 6 10 20 1 10 6 6 6 5 1 12 7 11 1 1 1 2 1 3 4 4 5 12 1 1 3 3 9 6 3 14 1 8 7 6 16 12 4 2 3 3 6 1 5 1 1 4 17 3 5 1...
output:
47 45 43 45 43 44 33 42 37 43 39 37 36 39 42 35 41 40 41 37 41 35 35 34 35 46 36 40 37 39 36 39 33 40 34 33 37 42 41 33 34 33 36 34 34 33 38 37 32 36 34 32 28 34 30 37 34 34 32 32 30 31 33 27 31 30 38 34 28 40 26 36 32 33 28 30 32 34 28 27 33 31 26 29 36 33 27 27 31 28 27 36 29 30 28 32 32 26 32 31 ...
result:
ok 32274 lines
Test #20:
score: 0
Accepted
time: 286ms
memory: 5280kb
input:
57560 196345 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 3 1 1 1 1 1 1 1 1 2 1 4 1 2 2 1 1 3 1 1 1 3 1 1 2 2 6 1 3 5 3 1 1 6 5 5 1 4 1 1 8 1 2 5 2 5 5 1 3 2 6 5 3 18 4 2 1 1 6 15 3 2 8 6 6 2 7 4 7 3 1 5 6 2 2 4 8 2 1 2 3 4 2 12 4 1 1 6 1 6 1 15 3 5 2 2 7 12 2 9 3 5 1 1 3 7 27 20 15 2 12 5 13 1 2 2 21 6 5 6 5 10...
output:
482 522 56984 52319 54021 484 455 449 420 412 56447 417 62 6 49729 57292 4155 44 55140 6021 57280 8733 56276 381 56520 368 370 350 356 13 6892 278 360 31835
result:
ok 34 lines
Test #21:
score: 0
Accepted
time: 291ms
memory: 6352kb
input:
62897 169366 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...
output:
34539 26796 22337 18729 14048 12335 10923 11935 8735 8550 7231 7803 8416 7263 6405 7104 7138 6337 6647 5576 5926 5746 4990 4960 5242 4885 5122 4662 5107 4790 4742 4662 4737 4392 4324 4228 4411 3844 3821 4054 3828 3729 3535 3360 3183 3263 3427 3349 3298 3158 2518 2960 2921 3055 2689 2724 2706 2646 24...
result:
ok 9962 lines
Test #22:
score: 0
Accepted
time: 168ms
memory: 4836kb
input:
60682 186488 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 2 1 3 2 1 1 1 4 4 1 2 1 1 1 1 2 4 7 1 1 11 1 5 3 1 2 1 1 1 1 3 3 1 1 4 2 1 2 4 2 6 4 5 2 3 15 3 3 1 3 11 3 12 4 11 6 4 4 4 1 2 1 5 2 6 6 1 2 19 3 6 3 7 1 3 2 2 2 4 14 1 3 1 1 1 8 5 2 4 2 4 11 4 3 1 1 11 8 8 1 2 6 8 2 4 5 8 3 4 12 17 11 14 2 10 1 3 5 14 ...
output:
22 493 25 497 36 40 57595 16 12 1 3 9 1 8 16 39 11 28 4 16 14 21 1 3 1 4 30 236 3 1 26 40 3 15 3 11 3 45 9 3 1 14 3 242 1 1 198 7 25 4 4 10 226 27 3 11 243 6 54515 7 243 25 19 4 21 6 241 14 13 4 26 28 5 13 36 20 15 12 7 3 19 4 13 22 31 70 221 3 11 4 15 1 225 219 23 216 6 225 5 14 17 57930 247 17 11 ...
result:
ok 258 lines
Test #23:
score: 0
Accepted
time: 1923ms
memory: 4580kb
input:
52117 188894 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...
output:
18158 16344 26191 34198 12698 33099 15027 22477 17386 23441 36612 37651 33783 34532 16777 44413 24364 21370 30529 49724 47220 33017 28454 10252 42074 7464 34933 26156 22524 25521 33472 10422 26670 15771 22323 36868 20066 21121 44693 46430 44305 36731 15059 3862 17439 22691 7997 34970 22986 36187 843...
result:
ok 188894 lines
Test #24:
score: 0
Accepted
time: 195ms
memory: 6356kb
input:
66038 176476 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 3 1 2 1 6 1 2 3 2 7 4 1 4 3 2 9 4 11 3 1 1 1 4 4 2 1 3 3 1 2 2 4 15 5 6 9 7 2 2 1 5 3 6 6 1 17 9 5 4 5 1 2 8 2 12 2 5 3 8 2 17 4 1 10 5 5 4 14 15 1 8 12 19 8 2 3 26 1 8 9 2 1 2 7 10 3 20 10 3 13 5 1 9 5 8 11 1 3 4 10 1 19 8 5 1 16 5 17 17 33 3 4 1 1...
output:
17 538 582 542 515 539 521 480 537 547 62577 22 424 491 11 445 496 484 457 435 472 433 446 412 423 440 460 428 405 425 8 413 389 404 31 388 346 397 20 10 36 1 381 39 374 305 14 399 23 64 392 370 349 347 328 371 368 396 348 374 266 7 363 312 387 386 38 368 287 365 315 24 326 370 5 309 363 319 345 362...
result:
ok 821 lines
Test #25:
score: 0
Accepted
time: 102ms
memory: 5184kb
input:
73751 186505 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 2 2 1 1 1 1 2 1 1 1 2 1 1 1 1 1 4 1 1 1 2 1 4 3 4 1 1 3 2 2 2 3 6 3 5 4 1 1 7 4 1 2 2 2 2 8 2 1 2 2 6 3 3 5 1 10 2 2 2 9 1 4 2 5 5 7 2 1 5 3 3 1 2 1 3 2 5 3 3 3 6 4 6 5 2 3 10 11 2 4 7 10 6 5 11 6 7 2 3 13 2 9 22 2 4 8 1 7 2 11 6 1 1 4 9 5 9 9 1 6 1 17 5 ...
output:
73 82 74 78 80 78 78 80 75 71 75 72 71 74 71 72 76 71 71 80 74 67 65 68 68 67 63 64 67 65 60 68 73 69 68 61 63 62 53 59 60 62 58 64 55 59 61 61 60 60 53 55 57 62 59 59 59 47 53 56 50 51 55 54 58 48 54 51 53 54 55 53 51 43 46 56 52 53 44 42 45 49 46 49 47 52 51 46 45 39 51 54 42 42 51 42 44 39 45 42 ...
result:
ok 20722 lines
Test #26:
score: 0
Accepted
time: 2530ms
memory: 5740kb
input:
73031 196038 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...
output:
47364 37196 32868 11129 17755 16034 16750 6247 5189 13981 14125 11643 1348 10528 9300 10119 8642 8054 8827 72770 8967 641 8506 6422 6981 7356 7286 1180 6836 6083 1231 194 7070 6895 7208 6444 6100 6264 2550 401 5719 5626 630 4788 5505 4681 4864 41770 5100 504 4128 4191 4057 4267 5301 4175 71899 4486 ...
result:
ok 167 lines
Test #27:
score: 0
Accepted
time: 107ms
memory: 6228kb
input:
81574 196519 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 4 1 4 1 2 3 1 2 1 2 1 3 1 2 1 4 6 1 1 2 1 8 1 1 3 9 2 1 5 6 3 4 10 6 2 1 12 6 2 5 13 9 1 4 4 2 4 1 4 7 2 1 5 3 5 1 5 1 8 7 2 2 14 2 11 21 14 3 7 5 3 4 9 8 5 4 20 2 6 10 4 7 3 6 1 2 2 2 7 8 1 1 2 10 6 11 3 1 25 4 12 12 10 4 16 3 5 7 1 6 6 7 3 28 15 4 3 20 8 ...
output:
56 64 60 58 62 62 56 61 57 66 59 63 60 60 57 62 57 58 57 59 58 61 62 59 48 49 63 51 62 59 55 52 54 59 59 59 58 58 63 56 58 48 62 54 53 59 58 57 62 56 55 55 49 52 62 50 53 51 47 56 54 45 59 50 51 53 39 50 49 55 45 53 47 43 54 54 63 48 55 50 47 50 46 42 49 48 44 48 43 38 41 44 47 47 48 44 52 47 45 51 ...
result:
ok 32753 lines
Test #28:
score: 0
Accepted
time: 314ms
memory: 5432kb
input:
85913 189305 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 2 1 1 3 1 2 3 2 2 2 1 1 2 1 1 1 3 5 3 3 4 2 2 2 3 2 3 1 2 3 1 6 2 1 2 1 1 2 3 8 5 3 8 2 1 4 2 5 6 1 1 12 3 2 1 7 6 2 2 3 1 1 2 5 4 6 9 1 8 8 9 4 14 10 9 15 8 5 2 13 5 14 2 12 7 2 20 4 14 7 4 13 9 10 5 11 1 5 4 2 1 2 7 4 3 1 6 4 2 21 1 2 9 20 7 7 4 2 7 1...
output:
642 8295 593 35 112 83243 11 576 608 34 18 39 584 533 501 516 532 2485 82892 54 79315 9 85168 487 81000 419 422 1121 84890 85374 433 455 115 431 12114
result:
ok 35 lines
Test #29:
score: 0
Accepted
time: 100ms
memory: 6484kb
input:
89431 189439 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 2 4 1 2 2 2 6 1 2 4 1 2 1 5 1 1 1 1 1 1 5 6 2 6 5 1 2 2 2 5 2 4 1 4 3 2 5 5 3 3 1 2 1 7 1 5 4 4 1 1 9 1 1 5 3 3 7 10 9 1 5 2 1 6 8 8 6 7 3 3 10 6 12 4 15 10 3 2 2 12 1 19 8 10 12 3 2 7 2 1 1 4 14 19 5 10 9 3 30 2 4 7 3 1 2 1 2 1 7 12 4 11 6 1 7 8 6 8 9 ...
output:
43 47 49 46 43 47 45 48 50 41 44 41 49 43 43 44 40 48 43 41 42 43 42 36 45 41 41 39 45 43 42 43 41 41 46 43 46 42 43 34 42 43 44 45 39 48 42 36 43 40 43 45 39 38 37 35 40 37 44 40 40 44 35 32 41 37 40 43 37 41 37 40 42 35 37 39 41 32 44 36 40 38 40 38 30 39 41 34 38 45 33 34 40 43 41 40 38 35 32 33 ...
result:
ok 37887 lines
Test #30:
score: 0
Accepted
time: 258ms
memory: 6624kb
input:
86886 199524 1 1 1 1 1 1 1 1 1 1 1 1 2 3 1 1 2 1 2 1 4 3 4 1 2 5 7 1 3 3 3 2 6 2 5 2 3 3 2 2 5 1 5 4 3 1 1 1 2 1 2 5 1 2 5 2 1 1 6 3 2 5 2 4 6 4 15 2 7 10 1 6 4 1 5 1 6 2 8 4 2 1 8 6 8 3 16 8 6 7 1 2 1 1 3 2 6 1 3 1 10 4 1 9 4 3 2 6 7 6 4 17 2 13 2 1 2 9 8 4 2 11 11 19 3 1 16 19 2 17 10 16 3 1 3 24 ...
output:
650 16 555 564 83736 591 550 32 148 487 7 91 49 32 502 498 29 17 455 7 12 455 442 392 13 15 417 80904 29 426 63 52 426 415 400 385 382 425 78 84506 348 416 377 384 385 431 2285 426 384 358 416 13 355 399 398 390 378 17 17 12 402 397 376 391 10 10 377 373 380 398 397 368 399 368 362 339 21 44 365 379...
result:
ok 176 lines
Test #31:
score: 0
Accepted
time: 110ms
memory: 5264kb
input:
95660 187672 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 3 1 1 2 5 3 3 6 4 4 1 1 1 5 4 3 2 3 4 7 7 1 1 3 6 1 6 1 1 6 17 1 4 4 10 5 10 6 5 1 1 2 8 8 9 23 4 3 6 9 8 1 1 1 3 2 1 1 1 4 3 1 4 12 3 18 2 3 3 2 6 1 21 2 7 8 8 2 1 5 9 10 21 6 7 6 3 19 9 5 1 7 1 15 2 8 8 3 1 9 6 6 7 2 11 15 44 4 5 24 13 21 1 16 1...
output:
100 91 95 100 94 94 89 93 86 86 92 88 95 85 92 96 89 91 95 83 84 84 84 86 87 82 82 90 80 88 80 90 85 81 87 80 84 87 90 81 78 84 77 76 84 76 91 78 78 85 82 77 74 80 86 80 81 81 80 72 84 76 71 68 71 71 77 73 73 71 68 72 67 80 71 74 66 73 75 68 78 73 76 71 80 72 62 67 71 79 66 67 72 67 56 72 74 66 68 6...
result:
ok 18767 lines
Test #32:
score: -100
Time Limit Exceeded
input:
86200 196707 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...