QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#800122 | #9632. 联通块 | A_programmer | 100 ✓ | 941ms | 90552kb | C++20 | 4.9kb | 2024-12-05 22:01:23 | 2024-12-05 22:01:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int MAX_N = 2e5 + 5;
const int N = 3e5 + 5;
vector<int> g[maxn], H[MAX_N], tmpq[MAX_N], que[MAX_N];
int ST[17][maxn], U[maxn], V[maxn], dep[maxn], dfn[maxn], siz[maxn], idx;
void dfs(int u, int fu)
{
ST[0][dfn[u] = ++idx] = fu, dep[u] = dep[fu] + 1, siz[u] = 1;
for (int v : g[u]) if (v != fu) dfs(v, u), siz[u] += siz[v];
}
inline int get(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
inline int lca(int u, int v)
{
if (u == v) return u;
if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
int d = __lg(v - u++);
return get(ST[d][u], ST[d][v - (1 << d) + 1]);
}
inline int dis(int u, int v) { return dep[u] + dep[v] - (dep[lca(u, v)] << 1); }
inline pii merge(const pii &a, const pii &b)
{
int au = a.first, av = a.second, bu = b.first, bv = b.second, cu = au, cv = av, nl = dis(au, av), tl;
if (!au && !av) return b; if (!bu && !bv) return a;
if ((tl = dis(bu, bv)) > nl) nl = tl, cu = bu, cv = bv;
if ((tl = dis(au, bv)) > nl) nl = tl, cu = au, cv = bv;
if ((tl = dis(bu, av)) > nl) nl = tl, cu = bu, cv = av;
if ((tl = dis(au, bu)) > nl) nl = tl, cu = au, cv = bu;
if ((tl = dis(av, bv)) > nl) nl = tl, cu = av, cv = bv;
return make_pair(cu, cv);
}
pii S[17][maxn], vl[N];
inline pii query(int l, int r) { int k = __lg(r - l + 1); return merge(S[k][l], S[k][r - (1 << k) + 1]); }
vector<pii> tmp, Qd[MAX_N];
int stk[MAX_N], res[N], tp;
inline void dfs2(int u, int fu)
{
stk[++tp] = u;
for (int i : tmpq[u])
{
int d = dis(vl[i].first, vl[i].second);
que[stk[tp - d]].emplace_back(d);
}
for (int v : H[u]) if (v != fu) dfs2(v, u);
tp--;
}
bool vis[MAX_N];
int sz[MAX_N], son[MAX_N], rt, SS;
inline void findrt(int u, int fu)
{
sz[u] = 1, son[u] = 0;
for (int v : H[u])
if (!vis[v] && v != fu) findrt(v, u), sz[u] += sz[v], son[u] = max(son[u], sz[v]);
son[u] = max(son[u], SS - sz[u]);
if (son[u] < son[rt]) rt = u;
}
int dt[MAX_N], dv[N], tt[MAX_N], tv[N], dpt[MAX_N];
inline void DFS(int u, int fu)
{
dpt[u] = dpt[fu] + 1, dt[++dt[0]] = tt[++tt[0]] = u; for (int d : que[u]) dv[++dv[0]] = tv[++tv[0]] = dpt[u] + d;
for (int v : H[u]) if (!vis[v] && v != fu) DFS(v, u);
}
void Solve(int u)
{
tt[0] = tv[0] = dpt[u] = 0, vis[u] = 1;
for (int v : H[u])
{
if (vis[v]) continue;
dt[0] = dv[0] = 0, DFS(v, u);
sort(dv + 1, dv + dv[0] + 1);
for (int i = 1; i <= dt[0]; i++)
for (pii nw : Qd[dt[i]]) res[nw.second] -= upper_bound(dv + 1, dv + dv[0] + 1, nw.first - dpt[dt[i]]) - dv - 1;
}
for (int d : que[u]) tv[++tv[0]] = d; tt[++tt[0]] = u;
sort(tv + 1, tv + tv[0] + 1);
for (int i = 1; i <= tt[0]; i++)
for (pii nw : Qd[tt[i]]) res[nw.second] += upper_bound(tv + 1, tv + tv[0] + 1, nw.first - dpt[tt[i]]) - tv - 1;
for (int v : H[u]) if (!vis[v]) rt = 0, SS = sz[v], findrt(v, 0), Solve(rt);
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
int cid, n, m, q;
cin >> cid >> n >> m >> q;
for (int i = 1; i < n; i++)
{
int u, v; cin >> u >> v;
U[i] = u, V[i] = v;
g[u].emplace_back(v);
g[v].emplace_back(u);
H[n + i] = {u, v}, H[u].emplace_back(n + i), H[v].emplace_back(n + i);
}
dfs(1, 0);
for (int i = 1; i <= n; i++) S[0][dfn[i]] = make_pair(i, i);
for (int i = 1; i <= 16; i++) for (int j = 1; j + (1 << i) - 1 <= n; j++)
ST[i][j] = get(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]);
for (int i = 1; i <= 16; i++) for (int j = 1; j + (1 << i) - 1 <= n; j++)
S[i][j] = merge(S[i - 1][j], S[i - 1][j + (1 << (i - 1))]);
int ID = 0;
while (m--)
{
int k; cin >> k; tmp.clear();
tmp.emplace_back(make_pair(1, 1)), tmp.emplace_back(make_pair(n + 1, 0));
for (int i = 1; i <= k; i++)
{
int eid; cin >> eid;
int x = dep[U[eid]] > dep[V[eid]] ? U[eid] : V[eid];
tmp.emplace_back(make_pair(dfn[x], 1)), tmp.emplace_back(make_pair(dfn[x] + siz[x], 0));
}
sort(tmp.begin(), tmp.end());
int lst = 1; tp = 0;
for (pii nw : tmp)
{
if (lst < nw.first) vl[stk[tp]] = merge(vl[stk[tp]], query(lst, nw.first - 1)), lst = nw.first;
if (nw.second) stk[++tp] = ++ID; else tp--;
}
}
m = ID; for (int i = 1; i <= m; i++) tmpq[dep[vl[i].first] > dep[vl[i].second] ? vl[i].first : vl[i].second].emplace_back(i);
tp = 0, dfs2(1, 0);
for (int i = 1; i <= q; i++)
{
int u, r; cin >> u >> r, r <<= 1;
Qd[u].emplace_back(make_pair(r, i));
}
SS = (n << 1) - 1, son[rt = 0] = 0x3f3f3f3f, findrt(1, 0);
Solve(rt); for (int i = 1; i <= q; i++) cout << res[i] << "\n";
return 0;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 26472kb
input:
1 500 25 500 160 300 95 345 131 498 259 359 400 394 445 137 75 145 126 185 86 336 44 98 271 32 73 227 2 1 39 420 487 38 356 240 447 193 70 26 46 171 436 272 260 485 393 66 297 351 192 88 326 245 174 416 4 9 399 194 58 350 256 176 376 248 2 59 77 7 59 148 258 173 352 34 9 320 221 244 3 1 284 193 335 ...
output:
456 450 12 500 153 8 4 33 3 10 432 500 420 396 93 228 2 500 20 340 6 475 1 0 13 256 500 308 396 15 421 500 500 500 32 67 450 128 500 153 420 2 0 432 18 6 92 308 85 500 0 1 33 500 8 228 500 1 367 475 228 450 500 432 420 218 142 20 500 8 14 500 500 218 500 341 456 450 37 4 0 1 1 162 228 500 500 99 148...
result:
ok 500 lines
Test #2:
score: 10
Accepted
time: 0ms
memory: 26352kb
input:
1 500 25 500 107 126 144 226 2 94 361 236 47 21 11 277 387 350 45 70 274 258 159 95 104 78 349 419 251 66 164 435 181 46 55 24 355 393 404 234 306 153 191 308 54 74 106 36 58 84 45 14 73 348 114 163 346 16 391 74 6 4 320 70 254 482 469 36 118 212 17 27 85 148 109 28 18 48 26 19 172 176 312 208 11 18...
output:
429 18 171 447 326 14 500 500 2 347 24 308 232 395 369 447 500 101 16 470 447 149 447 424 10 326 52 500 470 40 42 500 500 210 470 422 161 470 500 0 6 20 161 0 177 42 308 104 500 46 500 1 0 231 447 8 22 422 115 3 500 447 30 1 500 59 0 500 3 2 500 0 500 8 2 54 395 53 447 1 500 114 422 106 231 3 232 2 ...
result:
ok 500 lines
Test #3:
score: 10
Accepted
time: 0ms
memory: 26412kb
input:
1 500 25 500 189 213 447 219 35 251 109 395 46 18 169 115 36 57 413 28 66 8 489 124 409 10 118 15 143 150 256 461 317 273 22 29 107 3 113 133 88 109 478 88 158 150 160 41 233 435 238 166 89 137 77 250 50 101 134 84 327 172 107 151 122 176 70 282 120 146 361 150 450 64 5 16 93 56 101 175 373 194 426 ...
output:
95 8 0 18 36 469 0 500 453 403 442 53 500 500 500 10 2 10 3 469 95 366 5 227 154 43 48 4 23 470 432 88 12 0 3 357 500 396 0 0 59 470 59 154 0 348 3 231 348 0 348 469 5 6 1 442 500 475 38 0 61 27 211 442 213 147 21 397 4 7 469 475 147 9 43 442 396 500 43 67 231 12 18 357 357 20 470 500 80 192 6 17 1 ...
result:
ok 500 lines
Test #4:
score: 10
Accepted
time: 3ms
memory: 26360kb
input:
1 500 25 500 26 34 239 252 92 80 252 254 308 304 33 44 395 408 98 105 245 237 9 6 490 494 84 89 452 458 387 397 15 11 306 313 120 115 138 149 263 272 264 266 320 323 91 88 204 191 344 334 493 482 255 259 238 234 282 292 213 225 346 357 191 197 434 445 492 495 136 137 71 78 442 449 477 464 196 188 12...
output:
335 500 97 240 500 500 9 19 368 0 500 172 500 500 196 500 1 213 368 339 500 500 318 500 20 247 279 500 65 426 500 42 2 500 56 187 30 500 500 149 500 500 500 500 302 329 500 0 500 500 0 500 0 380 339 55 500 500 500 208 265 500 23 308 500 317 318 44 307 500 500 380 420 314 193 500 500 500 500 348 500 ...
result:
ok 500 lines
Test #5:
score: 10
Accepted
time: 0ms
memory: 24332kb
input:
1 500 25 500 413 417 57 48 425 422 35 46 144 149 429 435 113 123 350 342 364 360 290 303 68 81 178 168 280 281 160 165 102 104 488 477 229 237 133 129 129 119 196 187 190 177 225 226 405 414 117 124 180 177 153 140 450 457 206 211 32 43 13 14 183 188 361 363 398 388 149 155 185 175 410 404 254 266 1...
output:
246 500 500 500 500 292 175 500 500 419 32 305 500 500 500 164 500 257 500 133 500 500 419 500 330 500 292 296 399 500 346 500 0 500 376 500 247 41 500 500 500 330 19 500 163 252 500 80 500 500 500 500 152 500 409 0 18 500 457 366 500 475 9 3 500 3 500 500 500 500 500 113 500 500 500 3 500 0 58 151 ...
result:
ok 500 lines
Test #6:
score: 10
Accepted
time: 6ms
memory: 26356kb
input:
1 500 25 500 409 413 381 371 55 47 395 400 497 487 305 302 168 166 405 395 202 191 340 337 422 421 449 443 191 179 422 431 297 289 382 384 269 280 495 483 110 121 189 196 277 289 141 149 400 412 310 313 47 54 50 46 237 241 460 467 92 93 494 489 228 216 146 156 43 34 328 327 298 308 170 181 6 8 158 1...
output:
500 62 500 96 500 16 470 500 21 398 81 500 105 390 398 500 500 112 363 268 4 500 267 500 500 500 500 500 1 500 500 18 390 378 500 500 13 117 52 500 500 500 500 212 500 14 27 500 396 391 63 375 500 222 189 18 500 312 500 500 500 500 279 500 107 500 500 500 312 500 500 219 500 279 195 99 252 29 500 50...
result:
ok 500 lines
Test #7:
score: 10
Accepted
time: 3ms
memory: 26340kb
input:
1 500 25 500 172 183 392 411 20 24 330 339 146 182 58 67 61 111 381 419 114 96 213 261 187 162 260 287 144 109 108 72 90 81 217 181 148 166 365 393 280 300 368 334 362 361 149 93 209 212 208 169 200 144 49 10 50 38 218 160 350 370 327 278 249 218 38 44 124 179 46 44 280 251 415 441 462 484 468 494 2...
output:
66 98 456 500 223 340 169 216 434 51 8 33 16 208 77 78 500 173 133 500 192 0 195 141 107 88 500 96 20 190 374 144 80 500 360 318 500 441 14 500 150 5 500 220 234 14 13 58 8 9 500 0 158 0 281 500 304 334 340 263 15 307 277 318 400 500 0 71 15 426 2 10 0 500 159 202 225 132 27 3 25 500 157 99 475 0 11...
result:
ok 500 lines
Test #8:
score: 10
Accepted
time: 0ms
memory: 26344kb
input:
1 500 25 500 170 187 162 177 145 94 366 379 9 14 354 397 427 404 289 246 67 106 93 86 459 429 148 193 228 225 354 395 151 111 458 405 243 280 449 477 483 493 464 489 27 24 252 271 166 141 344 301 12 6 410 378 6 2 54 98 396 346 120 175 400 437 109 97 86 130 264 227 381 380 155 179 407 379 264 302 19 ...
output:
500 2 500 67 343 475 128 197 5 219 430 500 314 293 409 53 351 12 122 351 444 37 475 8 39 62 250 253 343 471 338 12 270 475 500 31 500 307 74 500 289 22 0 500 500 197 500 8 500 427 7 500 500 22 191 0 343 430 500 300 44 43 2 47 26 338 341 6 15 2 7 92 237 253 13 79 216 29 96 301 475 430 9 13 2 500 19 2...
result:
ok 500 lines
Test #9:
score: 10
Accepted
time: 3ms
memory: 26472kb
input:
1 500 25 500 209 246 129 88 12 14 320 271 296 300 48 55 155 156 386 406 95 85 139 85 152 144 370 398 412 369 88 142 154 142 484 457 170 113 439 425 363 332 18 30 302 279 277 316 276 255 249 260 366 345 308 357 3 11 364 368 466 413 383 374 18 17 479 440 88 86 80 102 118 92 205 214 498 450 430 388 173...
output:
202 251 500 126 157 346 295 44 500 5 56 123 329 4 64 392 465 264 298 500 4 5 154 13 249 6 212 289 39 64 500 412 36 10 465 23 1 81 2 138 500 500 304 500 0 251 404 425 130 500 0 11 369 288 32 241 271 500 102 241 128 460 0 384 401 228 66 5 13 9 124 80 384 427 21 253 384 11 249 355 86 1 154 332 276 3 39...
result:
ok 500 lines
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #10:
score: 10
Accepted
time: 3ms
memory: 26852kb
input:
2 2000 50 2000 1423 1355 1791 890 145 1295 637 1018 413 1025 1127 649 955 904 108 55 893 971 1952 1944 400 41 453 357 731 95 291 368 40 1442 899 1022 1406 1862 547 1388 577 102 1035 1183 196 881 286 882 1022 1078 832 110 272 626 1326 197 636 569 29 19 188 241 219 82 1237 1334 44 53 113 44 354 9 132 ...
output:
5 2000 187 8 2000 65 323 2000 254 5 1449 2 188 146 1920 1704 2000 113 1664 47 31 37 3 984 2000 0 1920 17 0 373 1941 22 635 1 363 673 929 2000 361 282 0 3 1941 1402 2 1805 1878 934 1312 0 556 1402 2000 2000 1068 673 975 984 933 0 11 1068 2000 753 0 0 1 939 5 2000 1704 1711 2000 25 9 1676 2 1878 29 34...
result:
ok 2000 lines
Test #11:
score: 10
Accepted
time: 6ms
memory: 29028kb
input:
2 2000 50 2000 1142 1744 1321 1376 917 256 1413 493 422 199 1187 686 197 293 1846 1350 142 1535 197 114 1012 1847 468 591 378 291 255 79 1766 848 555 536 859 1098 727 96 1746 1038 1710 1684 273 407 336 1421 678 685 355 1602 648 1041 1071 9 1988 82 441 492 38 40 564 669 185 352 503 1961 472 1807 49 6...
output:
0 1915 0 4 753 2 1004 1389 83 331 1 1303 1212 1183 1915 220 13 2 1444 14 22 441 573 1821 131 0 1110 2000 448 8 746 168 201 1915 7 9 23 1863 1 11 2000 1371 1558 1004 22 245 1883 2000 1004 571 2000 0 307 1639 1883 2000 0 6 758 1858 1863 42 2000 1710 141 23 1832 2 88 294 2000 83 115 737 1453 48 1697 16...
result:
ok 2000 lines
Test #12:
score: 10
Accepted
time: 6ms
memory: 26924kb
input:
2 2000 50 2000 835 1292 1674 169 145 139 1267 570 415 1055 487 168 1274 788 58 41 115 414 1736 927 123 525 790 1368 902 1434 1916 1249 1019 1351 382 642 1837 1542 1759 774 971 1940 475 709 1457 1079 255 138 1479 1331 1884 431 346 1954 505 64 208 1361 662 129 1842 1385 251 952 1436 1456 60 1804 588 1...
output:
2000 2000 0 1789 1705 268 452 17 1705 2000 369 30 2000 1 1849 2000 0 2000 1870 2 1684 1892 2000 8 1 29 2000 2000 1910 18 2000 1910 18 2000 392 655 191 2000 1031 1419 2000 1218 2000 2000 2000 1710 2000 2000 1831 1849 12 498 712 2000 1798 9 0 155 294 2000 2000 1910 133 9 20 1667 2000 1833 2000 1870 43...
result:
ok 2000 lines
Test #13:
score: 10
Accepted
time: 0ms
memory: 28956kb
input:
2 2000 50 2000 1975 1973 1010 1000 1526 1536 271 257 193 202 1450 1455 1684 1699 1 2 698 699 799 788 1186 1187 917 921 534 531 1252 1254 1803 1811 627 621 186 191 818 813 1703 1712 616 625 1491 1501 567 560 882 892 1780 1769 1190 1186 1377 1392 1541 1555 660 672 400 411 167 180 1726 1723 1874 1883 3...
output:
611 110 2000 583 2000 106 2000 2000 2000 1906 1122 2000 1592 2000 2000 2000 2000 1219 518 2000 1933 1875 1837 2000 1749 650 2000 2000 142 2000 2000 1291 963 2000 2000 1897 2000 2000 533 2000 1900 1164 2000 2000 2000 2000 1909 2000 2000 1647 2000 1179 97 2000 1024 58 50 2000 1728 2000 1844 354 2000 2...
result:
ok 2000 lines
Test #14:
score: 10
Accepted
time: 3ms
memory: 31072kb
input:
2 2000 50 2000 491 501 1680 1681 1631 1646 1581 1577 1895 1901 1281 1280 667 662 1720 1722 696 708 918 919 1352 1357 213 221 255 245 1590 1599 1070 1068 96 83 497 509 401 399 1320 1314 418 426 704 719 1016 1006 1606 1607 1498 1496 47 40 908 904 1801 1796 1312 1316 1717 1720 520 527 424 423 1087 1078...
output:
1009 2000 2000 1468 1277 2000 2000 2000 2000 1728 2000 2000 2000 818 1372 541 2000 2000 2000 1158 2000 7 2000 1495 1656 2000 1946 207 708 1318 2000 1490 1948 1348 585 1728 2000 2000 145 1166 1292 2000 620 2000 2000 2000 1090 2000 2000 2000 1250 1001 2000 2000 769 1845 1284 2000 2000 1292 2000 1816 2...
result:
ok 2000 lines
Test #15:
score: 10
Accepted
time: 7ms
memory: 31076kb
input:
2 2000 50 2000 434 448 421 416 1268 1263 561 576 1132 1146 653 640 870 862 695 703 853 840 1064 1067 96 90 1430 1442 898 904 1607 1598 1316 1318 1238 1227 685 687 437 442 1260 1275 686 699 1388 1402 1993 1994 1237 1236 1984 1985 1387 1390 1711 1704 309 322 1896 1906 1834 1821 1376 1378 1304 1298 108...
output:
6 421 2000 2000 2000 2000 2000 2000 2000 2000 2000 1504 2000 2000 1083 2000 1116 2000 2000 1513 2000 2000 1670 1720 2000 1092 1055 2000 2000 2000 490 1098 2000 2000 2000 2000 1761 1474 933 1086 2000 1287 16 84 380 1782 2000 2000 460 54 2000 1145 2000 1393 1669 392 943 1791 561 1264 561 859 2000 2000...
result:
ok 2000 lines
Test #16:
score: 10
Accepted
time: 10ms
memory: 26952kb
input:
2 2000 50 2000 1536 1490 1623 1616 631 615 23 67 256 197 1800 1735 1164 1278 1144 1038 894 960 16 122 402 466 75 105 757 662 683 761 1162 1057 1139 1155 1605 1649 713 663 1047 991 845 860 925 841 1899 1870 1068 977 579 477 1165 1252 1741 1828 1397 1447 877 977 1391 1491 181 229 1614 1629 659 576 139...
output:
922 274 417 995 351 2000 1675 730 307 645 51 219 1 35 2000 1525 2000 3 2000 1687 1256 1368 669 51 312 105 1022 1368 2000 1194 2000 22 1742 40 3 47 194 727 2000 36 1604 261 363 2000 1150 16 922 57 1690 1950 717 503 1 23 444 1053 60 3 1112 48 1514 79 33 2000 168 381 0 2000 1138 168 402 856 380 1495 19...
result:
ok 2000 lines
Test #17:
score: 10
Accepted
time: 7ms
memory: 26924kb
input:
2 2000 50 2000 1059 1149 1395 1302 613 566 1443 1381 1975 1896 1839 1917 1346 1256 1027 920 1219 1309 1270 1340 1742 1682 42 51 1817 1729 260 175 683 653 1024 1106 1023 942 1735 1690 1645 1551 387 501 582 656 856 822 380 268 643 618 1285 1297 429 379 641 750 446 523 1205 1312 1412 1424 1768 1883 151...
output:
1284 1270 822 387 2 1947 2000 2000 1605 349 656 333 804 837 372 176 745 3 2000 1069 329 2000 1265 317 498 287 890 329 34 1877 1454 2000 1850 83 61 1947 106 2 837 1862 309 1247 2000 1634 423 1341 441 2000 129 1950 1590 73 1538 66 2000 1816 1705 44 504 1756 426 482 36 123 178 1398 132 1375 924 1097 10...
result:
ok 2000 lines
Test #18:
score: 10
Accepted
time: 5ms
memory: 29036kb
input:
2 2000 50 2000 1545 1576 413 412 1120 1136 1186 1142 1727 1839 1034 1051 1239 1183 543 591 1874 1858 1232 1174 475 401 853 933 1266 1348 1008 1007 1395 1366 952 891 1188 1165 1701 1726 1243 1229 521 450 552 544 673 690 696 750 682 783 1868 1800 1322 1426 905 897 677 756 978 1035 965 969 1448 1346 41...
output:
2000 9 467 543 18 1586 258 41 1058 1060 1124 2000 5 2000 138 1675 192 159 1718 1008 22 292 2000 956 2000 2000 1008 121 2000 33 153 963 2000 2000 30 2000 2000 1144 731 251 2000 82 2000 1641 53 1229 49 78 861 956 1633 28 2000 249 2000 34 965 1157 498 753 156 487 565 518 2000 612 2000 229 1806 2000 160...
result:
ok 2000 lines
Subtask #3:
score: 15
Accepted
Test #19:
score: 15
Accepted
time: 357ms
memory: 88464kb
input:
3 100000 316 100000 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 ...
output:
7116 18702 30685 89626 91900 68029 99856 24514 99856 21550 958 63513 67890 69627 81017 45120 25573 23339 99856 48788 69094 79557 76332 41540 65799 99856 90842 99856 32381 48306 69788 25982 99856 69144 99856 17666 77905 97107 86289 99856 85158 66764 63052 16065 95112 30243 64004 68333 76813 99856 910...
result:
ok 100000 lines
Test #20:
score: 15
Accepted
time: 349ms
memory: 90552kb
input:
3 100000 316 100000 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 ...
output:
10015 74652 50243 65090 73508 75718 99856 99856 99856 95576 29751 14262 57510 57264 99856 5937 38610 2328 77394 99856 89756 54138 80485 86024 32182 99856 59748 48953 66530 99856 84516 58145 99856 63032 80970 99856 99856 3945 99856 93385 12520 50127 87819 89913 47464 99856 81560 81019 53395 9623 3767...
result:
ok 100000 lines
Test #21:
score: 15
Accepted
time: 355ms
memory: 89328kb
input:
3 100000 316 100000 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 ...
output:
99856 99856 99856 99856 50718 99856 69275 24315 89556 87309 50041 93165 53745 25011 99856 42078 31147 99856 99856 53269 99856 70462 71903 15651 51108 77294 42794 76694 20334 99856 85737 88288 71878 46679 7090 56259 41696 54253 13634 99856 99856 35761 83738 63697 53828 38779 24648 88262 54147 88185 3...
result:
ok 100000 lines
Test #22:
score: 15
Accepted
time: 337ms
memory: 90016kb
input:
3 100000 20 100000 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 5...
output:
23346 93425 10413 100000 48330 100000 36951 80129 17434 100000 77500 100000 100000 118 30571 10398 85975 84256 24721 52893 100000 20739 24371 65027 93697 51684 100000 74085 99062 76826 100000 16064 67828 51049 51291 3299 59621 100000 32754 34095 26308 64825 38751 100000 76043 90337 71601 32142 95533...
result:
ok 100000 lines
Test #23:
score: 15
Accepted
time: 339ms
memory: 89852kb
input:
3 100000 20 100000 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 5...
output:
76843 59847 56242 37475 100000 100000 50097 57146 95889 68810 93468 91438 82945 85819 75690 100000 86824 100000 29266 100000 21464 80995 1636 100000 32757 83791 98372 28301 100000 100000 74010 100000 69931 2766 24305 45797 100000 31395 100000 56939 73636 91193 100000 48603 100000 89533 65137 100000 ...
result:
ok 100000 lines
Test #24:
score: 15
Accepted
time: 330ms
memory: 89200kb
input:
3 100000 20 100000 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 5...
output:
100000 100000 98884 22455 3777 99477 74993 69573 77981 92696 90334 37440 100000 5712 100000 45897 45667 100000 100000 88979 42527 89482 100000 64273 89918 65626 37836 37387 100000 57577 46959 13268 40920 33974 62514 51743 100000 81962 76080 93652 92825 51070 100000 79023 79748 83708 24836 72715 3455...
result:
ok 100000 lines
Test #25:
score: 15
Accepted
time: 376ms
memory: 89924kb
input:
3 100000 5000 100000 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...
output:
87217 82002 100000 59429 74730 100000 78476 100000 62492 35730 3978 82420 66389 100000 82797 74837 86444 84263 69491 77263 60822 21044 100000 56671 53972 100000 78354 94901 19671 79256 22709 82427 42536 35257 100000 76139 100000 1431 66396 73077 93268 60577 81767 60303 28012 64072 71495 31360 100000...
result:
ok 100000 lines
Test #26:
score: 15
Accepted
time: 379ms
memory: 88628kb
input:
3 100000 5000 100000 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...
output:
100000 67436 79064 16131 81070 100000 58268 28248 100000 82149 65947 100000 59054 72152 70142 100000 100000 75403 100000 64722 100000 38772 21518 115 69310 47232 100000 8098 91011 55812 20884 87262 82372 52600 63500 100000 74300 100000 62227 74299 100000 93722 1199 57311 60543 100000 33144 100000 27...
result:
ok 100000 lines
Test #27:
score: 15
Accepted
time: 380ms
memory: 89664kb
input:
3 100000 5000 100000 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...
output:
83203 100000 66244 100000 56348 23615 100000 100000 100000 7549 84225 100000 86951 62679 87129 4189 74949 100000 78906 73386 58608 74219 61534 80287 30712 94467 100000 63398 35709 10548 64162 41104 77343 69569 38819 16872 53540 88081 88053 89054 38595 18183 52086 42475 52097 71060 100000 67187 14653...
result:
ok 100000 lines
Subtask #4:
score: 25
Accepted
Test #28:
score: 25
Accepted
time: 364ms
memory: 65768kb
input:
4 100000 50000 100000 83534 91958 44638 83107 30555 37613 47320 11817 17145 22205 3821 9581 12272 20812 293 1463 2550 2641 179 16579 28031 50662 15687 18932 6940 24780 31978 15599 17053 41795 56716 41026 32760 49030 96468 81779 44875 24089 67246 61768 44737 15873 64089 12670 7530 36388 68738 5284 32...
output:
21524 1 29017 1273 0 43127 49904 5 46274 50 54 5332 48504 33938 46141 100000 1097 1 4 473 29145 47147 49975 249 6436 385 100000 11564 49165 100000 5048 49968 21545 7628 100000 49957 27075 33909 194 34154 1 35144 100000 2 747 48824 49904 129 28 0 38866 45922 95 138 100000 100000 30070 0 1 51 1361 136...
result:
ok 100000 lines
Test #29:
score: 25
Accepted
time: 386ms
memory: 64460kb
input:
4 100000 50000 100000 77842 60502 68603 52317 31757 38542 84992 10892 9615 66890 24220 47013 43637 21910 64734 89003 82416 48686 35202 53940 71978 23016 10171 9981 45365 8667 15334 4983 96236 24780 64584 30356 56468 75646 27829 58014 47072 61318 2112 11409 32125 11754 12997 36312 40004 76860 59138 1...
output:
3 2 11352 39 49999 49823 55 1031 6345 11 45598 100000 2296 3651 100000 100000 28916 0 10 100000 80 100000 49962 49416 49910 1 100000 1485 2 100000 49966 49873 45884 28916 100000 11 100000 10722 47500 20 100000 124 12 100000 49952 2418 993 1 6 49802 262 100000 10099 7 2 11629 29224 49975 39534 100000...
result:
ok 100000 lines
Test #30:
score: 25
Accepted
time: 369ms
memory: 64720kb
input:
4 100000 50000 100000 1533 60 37566 46236 120 6020 26515 4541 87200 96476 99247 10073 10680 58234 51534 21685 71470 84409 85346 38908 2079 1572 279 13244 19816 6290 41410 45925 65690 96134 57550 50651 11322 24039 63056 69621 50998 62596 11627 12486 21194 29838 65222 14474 73767 98601 78758 78590 405...
output:
34 10 3351 2472 49515 15514 11193 12 49749 19828 492 3466 48567 44667 48470 813 5 54 100000 48414 100000 100000 3699 21596 7228 3 18159 24732 49992 39 6 1922 796 123 1 13018 2652 4 46671 9704 8205 14 100000 100000 48215 168 7696 1110 3234 272 2 100000 49221 48567 100000 4 49805 100000 100000 44659 4...
result:
ok 100000 lines
Test #31:
score: 25
Accepted
time: 517ms
memory: 68248kb
input:
4 100000 50000 100000 32448 32450 10131 10125 67127 67120 53244 53250 24856 24862 71953 71950 90216 90214 67227 67230 99550 99557 26703 26708 88211 88201 27040 27032 2724 2717 90632 90629 76881 76879 51851 51845 4343 4351 76105 76102 8472 8476 67900 67905 36064 36067 40447 40448 7701 7707 66772 6676...
output:
100000 3162 100000 30230 100000 100000 19783 12186 100000 100000 100000 100000 48918 45238 100000 100000 5609 100000 6077 100000 100000 19326 27346 100000 41334 100000 5527 100000 36445 100000 100000 100000 100000 37415 33257 31514 100000 100000 100000 100000 16402 36623 100000 100000 7010 100000 10...
result:
ok 100000 lines
Test #32:
score: 25
Accepted
time: 505ms
memory: 68232kb
input:
4 100000 50000 100000 94678 94685 1744 1741 3208 3218 13379 13386 39895 39891 99322 99330 88139 88148 7647 7640 60107 60102 47967 47977 19560 19552 74004 74009 98910 98901 27190 27187 17972 17973 21702 21706 23750 23745 90394 90396 44431 44425 76316 76324 46516 46512 35431 35434 81037 81042 58554 58...
output:
100000 100000 12982 100000 100000 15485 100000 46829 15847 6507 100000 42361 100000 100000 100000 100000 42721 41385 25323 100000 43909 22456 36571 31282 4480 100000 48327 100000 100000 100000 100000 17675 100000 43125 100000 35612 26546 31715 29345 100000 100000 100000 33055 13681 100000 30510 1000...
result:
ok 100000 lines
Test #33:
score: 25
Accepted
time: 510ms
memory: 68336kb
input:
4 100000 50000 100000 13347 13339 93472 93465 11588 11598 83781 83771 54305 54298 88935 88933 67285 67282 79181 79189 93584 93577 68025 68022 52603 52594 31534 31543 89422 89419 14893 14896 28485 28486 76814 76817 52443 52442 80504 80512 15821 15819 92174 92172 24309 24299 43107 43115 59039 59036 17...
output:
100000 27002 27859 100000 36217 17050 100000 100000 9305 100000 45031 39493 44602 35762 100000 48165 49163 100000 10902 11606 17379 48835 100000 12392 15215 46009 19891 100000 48647 100000 100000 100000 100000 37139 100000 100000 100000 100000 100000 100000 46329 100000 14107 638 100000 21486 41333 ...
result:
ok 100000 lines
Test #34:
score: 25
Accepted
time: 473ms
memory: 66116kb
input:
4 100000 50000 100000 27220 27613 80775 81268 26467 26663 44355 44572 14754 14751 80229 79684 4637 5185 14119 14337 32417 32329 98527 98598 61618 61605 43459 43613 21764 21206 59729 59471 62820 63177 26925 27348 23195 22936 31849 32039 23308 23246 11513 10993 80697 80441 25456 25350 82055 82624 1125...
output:
972 25600 49922 1759 640 2509 2789 822 31950 10300 38849 5933 100000 47412 46657 35821 6550 49494 2446 36967 25393 1873 47177 777 34240 100000 39986 32996 49015 17467 468 34140 10565 2 14570 144 907 792 825 11538 8169 39788 31026 34373 29877 2994 177 2206 32283 25383 9106 46596 20720 25062 100000 10...
result:
ok 100000 lines
Test #35:
score: 25
Accepted
time: 493ms
memory: 64748kb
input:
4 100000 50000 100000 4059 3474 43097 42893 48468 48283 82624 82818 73379 72972 75244 74728 20337 19911 14627 14498 2757 3229 33229 33025 56306 56660 40016 40100 99001 99580 3094 2587 67536 67564 76345 75987 79149 79076 65601 65131 5268 5575 56760 56228 66571 67189 57942 57675 80242 80787 9335 9145 ...
output:
31904 3726 34001 1517 1054 20674 21530 1158 19047 3948 35974 2493 100000 100000 45 36041 13167 39708 39814 9192 28770 5110 1223 114 473 9381 950 3957 3270 32871 34081 100000 38857 12319 634 24869 49898 4325 143 13449 5913 4853 9859 35109 13917 47876 27702 100000 4758 43357 37258 49879 10 13192 47337...
result:
ok 100000 lines
Test #36:
score: 25
Accepted
time: 500ms
memory: 65092kb
input:
4 100000 50000 100000 73044 73454 93691 93415 71325 71523 68734 69170 34031 33907 42247 41922 63665 63397 38988 39408 78269 78776 60822 60565 25802 25313 43737 44065 15601 15188 63478 63945 9357 9227 77914 77377 42493 43010 98915 98658 22217 22629 92131 92251 51899 51691 58874 58483 38940 39255 7896...
output:
19679 12051 1216 2151 12114 39706 127 718 22606 20481 14223 49946 100000 3278 37654 25905 18704 7472 3937 42656 14004 33286 1036 34 13240 47117 44906 28950 49794 3126 37025 39082 141 21756 49005 33525 3736 2637 243 6352 11 10036 2921 27496 28673 771 48153 50000 45654 6753 12682 2007 41221 100000 420...
result:
ok 100000 lines
Subtask #5:
score: 35
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #37:
score: 35
Accepted
time: 454ms
memory: 65888kb
input:
5 100000 316 100000 23794 39146 22697 66741 94669 68889 17521 61338 63842 52825 20565 88425 90608 20936 24876 12335 29694 15463 16163 43174 19793 25593 15593 17908 66865 13018 33219 87021 3059 1900 17252 56350 57600 49109 19330 30283 27034 41128 86135 49290 51688 15190 26660 8919 56502 28237 23935 2...
output:
9 77201 145 43 605 253 98951 61913 5 62604 99856 1 3474 6 254 68182 85646 66037 71133 98951 69902 92496 49889 827 176 18564 89526 5225 0 6198 8674 2 98951 99856 31 87828 4 99294 99856 89526 53 5104 6216 8 99856 401 99856 297 224 99280 13004 98161 88 99221 98312 25301 76038 99476 397 84341 14 1236 62...
result:
ok 100000 lines
Test #38:
score: 35
Accepted
time: 547ms
memory: 69648kb
input:
5 100000 316 100000 35731 35733 69762 69754 54042 54052 15451 15454 71859 71863 24192 24184 2157 2151 52705 52714 52175 52179 61591 61599 18579 18589 16159 16166 43610 43607 76431 76427 23761 23760 73401 73411 85035 85027 3606 3611 25136 25144 38652 38650 13315 13321 87617 87621 49441 49438 66810 66...
output:
67311 84226 66186 63413 37688 99856 99856 54779 78659 35330 79954 93458 99856 99856 99856 99856 35575 99856 6258 99856 99856 99856 86077 99856 99856 99856 27500 99856 99856 99856 99856 9404 99856 99856 99856 99856 62652 78230 99856 99856 99856 99856 59121 11817 9762 99856 20413 99856 96031 76356 998...
result:
ok 100000 lines
Test #39:
score: 35
Accepted
time: 564ms
memory: 69064kb
input:
5 100000 316 100000 24614 24619 23530 23535 13765 13768 89312 89316 72539 72532 10578 10586 25273 25282 77189 77187 76307 76308 49978 49969 52052 52042 49381 49389 32217 32226 11509 11518 83356 83349 19211 19210 96441 96450 46785 46784 33860 33866 40154 40144 38773 38772 7809 7813 70596 70587 94415 ...
output:
78111 99856 99856 99856 69716 78373 99856 99856 31540 99856 99856 99856 8063 96267 99856 99856 82843 99856 15407 99856 86902 99856 71229 99856 99856 99856 21583 82975 34285 99856 99856 99856 99856 99856 31643 99856 78813 99856 99222 37516 99856 99856 99856 95745 99856 74835 99856 99856 79385 99856 4...
result:
ok 100000 lines
Test #40:
score: 35
Accepted
time: 532ms
memory: 65284kb
input:
5 100000 316 100000 36479 35833 80324 80288 82999 83228 53545 52965 90992 91494 20365 20825 52606 52480 35974 36395 58375 58828 3015 3171 65255 64898 45751 46361 48843 48437 16121 16104 52066 52326 32467 32932 42315 41959 78170 77938 90063 89777 68829 68753 53217 52623 18172 18426 3206 3566 18692 18...
output:
66167 92854 222 70717 36004 75062 60795 23132 74669 780 66437 57970 1328 5179 99856 968 2251 806 44460 92812 72758 85637 99856 15037 48075 72815 99856 55200 44481 42588 49168 70514 8926 80942 47116 20771 9180 99856 53048 66405 53088 5096 99856 48057 2118 5154 99856 65831 2889 59337 9251 30831 1961 9...
result:
ok 100000 lines
Test #41:
score: 35
Accepted
time: 542ms
memory: 65812kb
input:
5 100000 316 100000 99235 98853 93750 94079 89263 89894 57418 57162 95350 95339 54893 54971 98581 98244 94634 94572 79442 79900 29966 29644 12234 11894 6925 7011 36834 36443 19889 20156 65624 66160 30470 30173 33541 33452 10962 10953 15953 15390 27747 27295 25219 25845 39767 39248 39507 39549 17382 ...
output:
64440 54552 69308 71683 21776 93760 21173 22 69360 43674 26718 59287 92421 50894 13606 577 99856 11100 64468 26578 52504 92607 81859 1410 65612 50751 2292 42297 99856 40968 5984 93111 25527 25852 84089 40502 5 99856 70599 1728 73283 72477 23106 54962 32346 26214 82975 352 34249 17413 51884 48266 799...
result:
ok 100000 lines
Test #42:
score: 35
Accepted
time: 458ms
memory: 66024kb
input:
5 100000 20 100000 61601 78976 8480 35996 2900 4490 32402 46468 14766 5277 8678 8671 62062 39866 90406 60873 11397 13581 15644 9290 3154 36203 16569 14450 11131 1891 10666 7022 3627 14468 35237 69884 24649 35216 12595 17636 31561 29178 19224 16725 62168 3819 34242 97295 19136 4746 23999 43879 16531 ...
output:
2 14322 29 31288 44 86287 97909 2487 356 21724 99944 2399 132 5428 95500 68144 16 20 87408 47 71962 6 29565 38966 94374 47 65210 79546 7 94340 98818 86021 7104 87791 12 99816 1010 5308 100000 1955 77970 99892 38926 100000 100000 99980 601 617 11 30821 99647 89978 1052 41 21123 5 90610 100000 3889 98...
result:
ok 100000 lines
Test #43:
score: 35
Accepted
time: 552ms
memory: 70068kb
input:
5 100000 20 100000 1342 1349 37640 37639 45877 45878 78332 78333 21484 21474 13801 13802 59570 59566 73931 73923 57631 57637 60889 60884 45602 45607 35865 35862 97617 97612 90212 90202 27887 27878 97274 97271 62494 62497 67320 67317 71745 71755 88665 88662 1544 1553 53066 53075 91559 91566 18097 180...
output:
37070 13884 96196 100000 100000 100000 65672 67310 51975 74849 21918 50480 100000 100000 73990 69136 100000 100000 100000 23751 100000 23888 30386 100000 100000 65774 100000 100000 69449 48250 100000 67132 53596 25327 63364 6915 73658 100000 100000 73912 100000 82194 15786 100000 100000 48929 92937 ...
result:
ok 100000 lines
Test #44:
score: 35
Accepted
time: 531ms
memory: 69760kb
input:
5 100000 20 100000 59264 59258 87717 87713 22225 22233 41776 41783 38511 38503 89421 89418 59191 59188 77388 77394 99756 99755 96467 96468 4932 4923 22680 22684 59939 59942 3231 3237 32666 32675 45931 45941 68555 68563 60047 60040 47510 47509 71398 71400 39997 40002 4827 4823 60948 60951 75322 75312...
output:
100000 100000 53450 100000 100000 59130 100000 100000 100000 1143 100000 40600 100000 100000 100000 100000 69054 79660 100000 100000 100000 69564 100000 100000 51779 100000 100000 96458 71497 100000 100000 100000 66287 100000 100000 24105 45060 99864 43341 42672 73213 5611 100000 77610 100000 79621 ...
result:
ok 100000 lines
Test #45:
score: 35
Accepted
time: 537ms
memory: 66572kb
input:
5 100000 20 100000 21461 21164 71167 70824 97255 97503 59623 59080 84738 85185 44114 44550 30324 30360 81441 81270 29850 30193 92272 92857 11808 12207 41553 41065 90015 90242 94350 94634 34000 33776 28572 28979 65660 65495 84076 83640 65227 65095 24103 23580 37412 37149 65839 66179 8898 9095 6723 62...
output:
73434 93433 47069 1759 66002 37763 22602 87270 0 100000 95679 17176 100000 98369 73678 96351 74314 2189 12154 100000 88797 56525 73048 19459 16041 13611 100000 75136 43 266 8861 97595 50759 11969 118 33131 32734 100000 71105 119 63382 72722 93256 3914 35262 98712 69440 59337 75790 89287 99917 72899 ...
result:
ok 100000 lines
Test #46:
score: 35
Accepted
time: 560ms
memory: 65968kb
input:
5 100000 20 100000 30830 30987 29641 29277 91951 91752 86037 85940 79136 79653 4107 4641 35199 34681 41861 41656 5908 6540 29918 30138 27729 27139 68760 68440 3860 4152 81759 81999 49031 49170 4614 4599 75309 75715 44343 44166 32087 32011 28265 28802 73643 74140 23214 22910 20216 20640 46607 46343 1...
output:
886 100000 35274 235 246 64317 68101 92 64459 20893 77364 24261 36518 17495 45099 37369 54489 1259 79595 49213 40215 2091 54551 42 5314 51671 7430 98748 4678 995 51376 62526 82896 72479 11251 60740 82476 100000 93977 6366 97875 18485 96082 1156 54979 34 83294 96857 23365 90673 67027 18202 45715 8241...
result:
ok 100000 lines
Test #47:
score: 35
Accepted
time: 437ms
memory: 66144kb
input:
5 100000 5000 100000 89950 61865 92146 17194 23378 6354 19068 26442 3036 8450 97249 47870 1413 56517 70272 629 24274 15792 67638 99264 56427 24852 7607 11615 39 5824 74572 92104 63647 89870 24535 79943 25040 75115 34710 25843 11751 4477 37612 45293 8918 6453 1016 3107 40912 61802 44481 30453 16400 9...
output:
919 11 6339 34230 3764 666 86361 22 15959 94118 100000 94881 3038 86263 4190 81887 14967 934 85462 2438 190 94337 863 0 37324 25480 203 1167 3158 100000 4 45256 12 57 2 16 94833 6 6145 0 100000 6 100000 41144 31 26 55072 71967 3774 100000 91870 290 7 58470 25121 95000 785 80618 92873 58 93463 17441 ...
result:
ok 100000 lines
Test #48:
score: 35
Accepted
time: 561ms
memory: 71004kb
input:
5 100000 5000 100000 85165 85169 86575 86565 25288 25291 49247 49246 85076 85073 33618 33608 62704 62695 18763 18755 75304 75313 3888 3889 92234 92244 12448 12440 94913 94911 18795 18805 98716 98722 62402 62400 12488 12487 63455 63454 13056 13064 29380 29382 85700 85703 71729 71725 59986 59996 69405...
output:
48038 25974 100000 100000 100000 21400 100000 100000 9263 62996 65410 38758 90367 75490 2834 100000 100000 100000 27629 9506 100000 45965 55865 100000 45511 68133 53328 100000 88324 2993 100000 100000 54622 13650 22464 100000 100000 38893 28099 100000 26722 28069 100000 91626 100000 100000 100000 10...
result:
ok 100000 lines
Test #49:
score: 35
Accepted
time: 566ms
memory: 69240kb
input:
5 100000 5000 100000 85690 85695 4099 4103 92471 92481 70406 70399 96641 96636 49712 49719 35442 35443 41413 41404 87428 87426 34247 34253 34758 34757 37596 37605 21128 21135 21900 21910 34748 34757 40288 40283 18622 18632 79848 79841 67275 67271 40991 40988 60576 60577 20748 20754 94379 94376 87474...
output:
100000 100000 100000 100000 74331 100000 879 21052 100000 100000 100000 100000 77185 4768 35808 100000 91727 88541 86660 100000 100000 100000 100000 32313 100000 100000 93215 100000 100000 43928 65754 76966 16 77184 100000 85011 100000 100000 67970 100000 100000 57699 7229 75837 84395 100000 94705 1...
result:
ok 100000 lines
Test #50:
score: 35
Accepted
time: 531ms
memory: 66516kb
input:
5 100000 5000 100000 35256 35062 93687 93723 21373 21942 31950 32049 13404 13173 71077 71691 94160 93713 70966 71112 84946 84304 6152 6452 85538 86080 92237 92673 80980 81182 35870 36287 85682 85693 35402 35771 98713 98160 19146 18543 856 955 91720 91203 34217 33691 80360 80266 56201 56335 62955 631...
output:
100000 19309 56810 84169 23855 26571 34507 65727 62312 12073 30622 41517 100000 72524 9153 11295 6928 2211 56676 86146 37265 1906 24328 24608 43825 59628 100000 62164 45377 100000 5383 65890 61417 5068 89535 100000 6006 22 85407 85 61728 1514 23446 100000 10853 8925 1915 26819 0 18453 2231 56466 711...
result:
ok 100000 lines
Test #51:
score: 35
Accepted
time: 560ms
memory: 65168kb
input:
5 100000 5000 100000 40326 40237 82510 82921 3255 2919 57214 57457 15713 15510 3712 4285 10172 10450 19602 19723 86063 85621 23568 23876 39998 40130 72647 72167 46400 46779 68591 68602 31093 31614 97900 97353 14724 15335 48298 48411 13860 13770 53707 53150 80521 79948 78513 78555 55703 56139 45206 4...
output:
59562 40154 59325 7116 39661 956 40297 39817 7209 14251 25914 83621 18438 52509 57633 94596 67827 85680 72528 100000 12 8261 60080 70680 66441 838 75417 79221 566 10663 100000 94881 100000 8130 53190 68767 32773 90395 77237 17629 81774 36360 490 28337 66155 19277 85371 21252 93321 37984 41715 54912 ...
result:
ok 100000 lines
Subtask #6:
score: 5
Accepted
Dependency #5:
100%
Accepted
Test #52:
score: 5
Accepted
time: 744ms
memory: 72120kb
input:
6 100000 3000 300000 24522 9089 42285 11117 6455 985 637 20347 21686 21193 66625 15902 81546 83181 224 175 11887 38177 91158 20556 76059 84399 2967 73086 18508 66441 19875 24675 12012 11534 82425 24704 29358 48319 31804 72664 13770 4137 43278 35101 2927 44385 11550 7417 78317 965 6969 6379 63283 796...
output:
430 241763 242666 297000 624 300000 34054 117562 38217 91342 20 300000 296901 258740 3 296581 273069 295888 2467 26483 291840 13738 21177 57 37595 300000 300000 207733 163939 296710 15 0 5728 188423 296727 295888 300000 296581 50884 349 300000 300000 19 572 207733 80 268930 300000 0 47790 295755 129...
result:
ok 300000 lines
Test #53:
score: 5
Accepted
time: 941ms
memory: 76656kb
input:
6 100000 3000 300000 85797 85796 72149 72142 21553 21554 93667 93663 10966 10973 60095 60098 43451 43460 8205 8210 19140 19135 29375 29365 73716 73711 56106 56111 63322 63332 41804 41810 30436 30432 38898 38905 29084 29091 73118 73127 67108 67104 88436 88440 19500 19495 49759 49754 61601 61607 36454...
output:
184106 82774 300000 272171 300000 300000 300000 256550 300000 300000 62309 204503 239874 300000 300000 252895 300000 236875 170780 173974 300000 300000 285297 300000 300000 300000 300000 276192 250065 300000 81406 300000 300000 300000 300000 192237 300000 63136 155126 264221 247459 142062 300000 300...
result:
ok 300000 lines
Test #54:
score: 5
Accepted
time: 870ms
memory: 71388kb
input:
6 100000 3000 300000 43156 43362 74429 73786 55797 55918 55626 55398 96268 96293 55284 55026 6571 6808 69286 68957 63793 63717 49324 49045 26719 27250 37255 36651 73268 73037 44786 44456 18080 18690 94876 95505 80729 80294 81889 82159 84578 83933 89571 89065 81102 80552 59597 59382 51589 51793 28357...
output:
14726 156406 209347 300000 50463 179421 37590 134550 99811 178888 133392 272747 124846 5016 14092 151830 278650 43162 9179 127988 69683 95590 10172 28863 243292 2315 2401 5992 115173 186237 12481 95002 29887 300000 131179 300000 192342 1505 0 26947 241 152815 246561 1264 218534 80221 249966 264642 3...
result:
ok 300000 lines
Test #55:
score: 5
Accepted
time: 724ms
memory: 72528kb
input:
6 100000 100 300000 56178 61223 19550 15322 21077 12277 2093 53 1641 11554 7649 61213 6431 2790 12351 34894 78933 72747 2113 5837 2384 433 70693 60724 11269 56788 71704 80110 36109 76638 39872 41293 37059 67110 33593 33422 20626 42747 30541 43987 59668 56664 37044 96199 93422 54898 75751 66473 17731...
output:
300000 85108 95701 282703 140745 75 2819 0 300000 133667 0 1955 291 5738 283049 298363 0 6 173918 32549 7 21 255 0 6704 300000 299748 300000 300000 8106 300000 364 262400 13305 300000 2824 300000 1792 6 68849 290727 300000 69 111986 291661 10 137 249630 0 283049 298818 232153 0 204402 14099 0 33 783...
result:
ok 300000 lines
Test #56:
score: 5
Accepted
time: 909ms
memory: 76508kb
input:
6 100000 100 300000 33374 33367 388 380 36644 36652 11055 11057 43638 43632 43932 43926 17054 17055 59769 59765 8027 8021 1675 1683 85648 85644 98844 98852 91914 91919 93235 93236 39042 39052 84484 84477 82473 82479 95522 95526 48696 48706 49376 49367 34407 34410 29868 29867 30512 30509 22691 22681 ...
output:
300000 207939 300000 136487 300000 300000 125407 300000 300000 300000 300000 197530 300000 300000 300000 300000 300000 45707 300000 208402 300000 300000 300000 300000 295506 300000 5259 300000 300000 300000 290685 300000 214834 300000 300000 191928 48417 215556 300000 300000 34772 300000 300000 1249...
result:
ok 300000 lines
Test #57:
score: 5
Accepted
time: 936ms
memory: 72536kb
input:
6 100000 100 300000 37965 38216 46332 46065 42847 42641 29308 28996 54716 54278 94221 94273 44066 43897 35776 35547 57531 57321 94121 94345 68624 68696 11632 11013 87323 87836 65617 65731 97906 98339 74072 74161 77580 77275 55148 54555 4074 3440 76377 75787 14882 14680 40712 41031 30530 30057 75589 ...
output:
2755 131795 131732 249003 117832 181265 300000 20968 65271 299572 274388 422 211847 3072 2141 238110 722 37849 52082 179539 47110 300000 68994 143877 273738 300000 113953 300000 25577 300000 300000 22958 184467 22503 54772 173712 300000 2235 17085 200620 28312 7922 26942 1241 139053 153226 552 30000...
result:
ok 300000 lines
Test #58:
score: 5
Accepted
time: 409ms
memory: 81280kb
input:
6 100000 15000 300000 2 1 3 2 4 2 5 3 6 2 7 4 8 1 9 1 10 9 11 4 12 3 13 9 14 8 15 1 16 4 17 15 18 4 19 10 20 18 21 3 22 7 23 6 24 4 25 16 26 19 27 12 28 21 29 1 30 3 31 10 32 31 33 18 34 27 35 15 36 23 37 17 38 22 39 1 40 9 41 34 42 39 43 11 44 12 45 42 46 9 47 9 48 32 49 20 50 43 51 50 52 51 53 52 ...
output:
109834 270000 12639 176354 5432 47124 251816 109834 1977 222319 285000 285000 25605 270000 5548 636 74498 285000 42352 270000 197523 84910 236955 285000 16114 285000 10905 285000 285000 176354 55357 270000 251816 251816 5612 270000 5584 11060 157024 109834 10596 236955 98934 71838 207589 285000 5234...
result:
ok 300000 lines
Test #59:
score: 5
Accepted
time: 406ms
memory: 83768kb
input:
6 100000 10000 300000 2 1 3 1 4 2 5 2 6 1 7 2 8 2 9 7 10 2 11 10 12 11 13 2 14 10 15 5 16 8 17 5 18 7 19 9 20 16 21 10 22 10 23 15 24 16 25 15 26 8 27 8 28 18 29 20 30 25 31 13 32 30 33 20 34 27 35 28 36 33 37 3 38 19 39 32 40 17 41 35 42 40 43 16 44 5 45 22 46 38 47 27 48 12 49 4 50 13 51 50 52 51 ...
output:
5718 254342 280000 290000 290000 63982 280000 290000 28723 22767 30982 153154 27730 290000 254342 280000 290000 56018 125229 112894 135183 30966 290000 41797 290000 152163 217279 290000 14657 290000 17165 26073 13916 8871 280000 152163 17288 224707 52602 290000 3306 224772 54018 290000 280000 13916 ...
result:
ok 300000 lines
Test #60:
score: 5
Accepted
time: 438ms
memory: 79740kb
input:
6 100000 30000 300000 2 1 3 1 4 2 5 4 6 1 7 1 8 1 9 3 10 2 11 7 12 2 13 4 14 1 15 7 16 6 17 15 18 16 19 1 20 16 21 12 22 10 23 17 24 12 25 19 26 9 27 17 28 23 29 25 30 10 31 10 32 1 33 5 34 24 35 8 36 15 37 18 38 28 39 6 40 34 41 22 42 22 43 42 44 7 45 3 46 9 47 38 48 10 49 25 50 10 51 50 52 51 53 5...
output:
26042 270000 6910 4827 100458 5033 117401 5811 240000 270000 230130 58312 43038 0 10777 43038 240000 20349 240000 270000 270000 39387 270000 678 117401 2219 235190 86394 8807 9661 270000 9796 235190 270000 5779 30333 44256 5631 230130 235190 35813 230130 235190 270000 270000 43038 235190 28569 18315...
result:
ok 300000 lines