QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #322819 | #2630. Railway Trip 2 | 5ab | 100 ✓ | 734ms | 88652kb | C++20 | 3.2kb | 2024-02-07 19:56:08 | 2024-02-07 19:56:09 |
Judging History
answer
/* name: 2630
* author: 5ab
* created at: 2024-02-07
*/
#include <iostream>
#include <tuple>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))
auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };
using ll = long long;
const int N = 1e5, lgN = 17, M = 2e5, S = 2 << lgN, INF = 1145141919;
int lp[lgN][N], rp[lgN][N];
struct seg
{
int mn[S], mnt[S], mx[S], mxt[S];
inline int ls(int x) { return x * 2; }
inline int rs(int x) { return x * 2 + 1; }
void build(int l, int r, int id)
{
mn[id] = l, mx[id] = r;
if (l == r)
{
mnt[id] = mxt[id] = l;
return;
}
mnt[id] = INF, mxt[id] = -1;
int mid = (l + r) >> 1;
build(l, mid, ls(id));
build(mid + 1, r, rs(id));
}
void chkmax(int L, int R, int l, int r, int id, int vl)
{
chmax(mx[id], vl);
if (L <= l && r <= R)
{
// cerr << id << " " << vl << endl;
return chmax(mxt[id], vl);
}
int mid = (l + r) >> 1;
// cerr << id << " " << vl << endl;
if (L <= mid)
chkmax(L, R, l, mid, ls(id), vl);
if (mid < R)
chkmax(L, R, mid + 1, r, rs(id), vl);
}
void chkmin(int L, int R, int l, int r, int id, int vl)
{
chmin(mn[id], vl);
if (L <= l && r <= R)
return chmin(mnt[id], vl);
int mid = (l + r) >> 1;
if (L <= mid)
chkmin(L, R, l, mid, ls(id), vl);
if (mid < R)
chkmin(L, R, mid + 1, r, rs(id), vl);
}
pair<int, int> query(int L, int R, int l, int r, int id)
{
if (L <= l && r <= R)
return { mn[id], mx[id] };
int mid = (l + r) >> 1, cmn = mnt[id], cmx = mxt[id];
if (L <= mid)
{
auto [lmn, lmx] = query(L, R, l, mid, ls(id));
chmin(cmn, lmn), chmax(cmx, lmx);
}
if (mid < R)
{
auto [lmn, lmx] = query(L, R, mid + 1, r, rs(id));
chmin(cmn, lmn), chmax(cmx, lmx);
}
// cerr << cmn << " " << cmx << " " << l << " " << r << " " << id << endl;
return { cmn, cmx };
}
}
T[lgN + 1];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> k >> m;
T[0].build(0, n - 1, 1);
for (int i = 0, x, y; i < m; i++)
{
cin >> x >> y, x--, y--;
if (x > y)
T[0].chkmin(max(y, x - k + 1), x, 0, n - 1, 1, y);
else
T[0].chkmax(x, min(y, x + k - 1), 0, n - 1, 1, y);
}
for (int i = 0; i < n; i++)
{
tie(lp[0][i], rp[0][i]) = T[0].query(i, i, 0, n - 1, 1);
// cerr << lp[0][i] << " " << rp[0][i] << endl;
}
int lgn = 1;
for (int c = 2; c <= n; c <<= 1, lgn++)
{
for (int i = 0; i < n; i++)
{
tie(lp[lgn][i], rp[lgn][i]) = T[lgn - 1].query(lp[lgn - 1][i], rp[lgn - 1][i], 0, n - 1, 1);
// cerr << lp[lgn][i] << " " << rp[lgn][i] << endl;
}
T[lgn].build(0, n - 1, 1);
for (int i = 0; i < n; i++)
{
T[lgn].chkmin(i, i, 0, n - 1, 1, lp[lgn][i]);
T[lgn].chkmax(i, i, 0, n - 1, 1, rp[lgn][i]);
}
}
int q;
cin >> q;
while (q--)
{
int l, r, y;
cin >> l >> y, l--, y--, r = l;
int ans = 0;
for (int i = lgn - 1; i >= 0; i--)
{
auto [nl, nr] = T[i].query(l, r, 0, n - 1, 1);
if (!(nl <= y && y <= nr))
{
ans += (1 << i);
l = nl, r = nr;
}
}
cout << (ans == (1 << lgn) - 1 ? -1 : ans + 1) << "\n";
}
return 0;
}
// started coding at: 02-07 19:05:35
詳細信息
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 4ms
memory: 20328kb
input:
300 1 260 297 130 184 244 219 208 54 52 143 285 187 241 230 197 264 163 274 153 223 204 129 299 149 279 279 148 180 183 203 208 226 201 162 266 34 32 169 259 291 136 213 215 159 154 293 134 177 251 296 131 185 243 254 173 268 159 188 240 180 175 164 264 252 175 242 185 225 202 83 80 180 248 220 207 ...
output:
1 1 1 1 155 1 1 100 51 75 4 1 -1 102 46 38 88 20 56 40 1 150 124 37 24 134 -1 114 173 14 72 18 1 86 114 71 80 -1 109 159 7 143 98 16 1 127 -1 117 8 22 173 141 19 78 18 1 73 23 34 1 134 13 1 126 117 89 35 1 41 74 7 88 80 135 97 -1 1 73 14 58 119 112 86 67 168 172 34 73 -1 116 132 101 98 85 141 99 -1 ...
result:
ok 300 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 22180kb
input:
300 1 278 259 141 8 7 109 292 89 85 183 218 198 203 260 140 211 189 84 79 188 213 109 111 78 76 146 255 91 90 204 196 40 38 70 68 199 202 102 299 219 181 253 147 265 135 258 142 218 182 144 257 168 233 251 149 257 143 176 225 25 22 177 224 262 138 216 184 75 73 108 293 163 238 137 264 214 186 236 16...
output:
146 109 122 118 64 13 59 105 38 15 192 20 113 -1 68 150 -1 -1 24 209 117 66 119 115 1 1 159 19 148 147 183 167 178 140 106 -1 22 9 40 49 182 2 25 1 159 52 166 -1 129 70 -1 69 1 121 158 42 64 66 90 163 159 99 104 167 147 1 105 152 94 90 23 107 138 -1 87 86 -1 91 152 177 115 79 133 147 132 68 143 187 ...
result:
ok 300 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 22268kb
input:
300 1 300 10 280 180 109 170 119 182 107 55 235 174 115 255 34 110 180 121 169 177 112 67 223 293 294 27 263 208 81 122 168 157 132 86 204 64 226 83 207 115 175 111 179 1 289 258 31 45 245 137 153 108 182 236 53 163 126 244 45 149 140 106 184 11 279 257 32 59 231 214 75 183 106 256 33 93 197 246 43 ...
output:
229
result:
ok single line: '229'
Test #4:
score: 0
Accepted
time: 0ms
memory: 26356kb
input:
300 100 300 178 221 18 94 22 116 3 136 286 252 186 269 253 152 250 171 270 247 202 187 43 7 290 239 270 151 106 18 190 277 252 167 292 182 156 244 146 81 198 275 263 229 169 289 298 278 59 126 86 108 255 279 109 100 37 73 92 29 102 116 28 77 125 144 96 133 170 159 206 226 8 138 250 184 248 284 119 1...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 300 lines
Test #5:
score: 0
Accepted
time: 4ms
memory: 18204kb
input:
300 2 298 93 95 215 217 213 215 299 297 47 45 113 115 125 127 57 59 21 19 267 269 295 297 73 71 233 231 241 243 39 37 63 61 123 125 275 277 217 219 81 79 163 165 25 27 209 211 105 103 45 47 5 7 89 91 71 69 291 293 281 279 25 23 213 211 183 185 265 263 1 3 11 13 103 105 211 213 177 179 3 1 229 227 29...
output:
53 41 71 57 105 22 4 33 10 98 75 105 82 63 103 145 65 8 59 14 94 108 32 60 99 67 28 34 27 16 3 44 18 47 103 51 48 84 7 24 101 72 82 82 104 38 34 79 88 15 8 80 60 48 53 69 8 49 29 -1 59 66 68 63 17 52 50 102 54 84 96 42 76 75 68 46 83 95 77 61 29 45 21 100 30 57 67 57 19 79 5 37 49 4 25 89 22 13 93 9...
result:
ok 300 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 20288kb
input:
300 299 300 284 1 59 300 9 300 261 1 89 300 205 1 127 300 185 1 10 300 3 300 137 300 270 1 85 300 64 300 159 1 288 1 120 300 24 300 18 300 90 300 46 300 23 300 241 1 225 1 285 1 256 1 282 1 154 1 186 1 218 1 219 1 281 1 132 300 300 1 73 300 57 300 6 300 280 1 116 300 71 300 194 1 65 300 111 300 293 ...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 300 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 18196kb
input:
290 271 300 215 165 68 34 135 270 267 8 109 239 145 98 246 108 27 6 128 192 170 212 17 230 110 27 79 20 23 7 105 61 159 153 148 279 72 16 86 218 30 57 103 202 223 170 65 220 217 64 238 174 98 11 41 256 86 139 55 5 117 278 96 44 156 24 250 22 8 68 149 152 197 161 177 169 28 125 125 229 78 73 227 36 2...
output:
2 1 2 1 1 1 2 1 2 1 1 2 2 2 2 1 2 1 1 1 1 2 1 1 2 2 1 1 1 2 2 1 2 1 2 1 2 1 1 1 2 1 2 2 1 1 2 1 2 1 2 1 1 1 2 2 2 2 2 1 2 2 1 2 2 2 2 2 2 1 2 1 1 2 1 1 1 2 1 1 2 1 2 2 2 1 2 1 2 1 2 2 1 1 1 1 2 2 2 2 1 1 1 1 2 1 2 1 1 2 1 2 1 1 2 2 2 2 1 1 2 2 2 1 2 2 2 1 2 2 2 2 1 2 2 1 2 1 2 1 1 1 1 2 1 2 2 2 2 2 ...
result:
ok 300 lines
Test #8:
score: 0
Accepted
time: 4ms
memory: 20320kb
input:
300 294 300 41 122 154 294 41 224 244 121 201 83 144 83 40 228 113 43 188 173 18 176 156 16 279 96 139 244 76 99 18 39 188 179 10 216 289 13 34 103 101 124 288 265 259 298 71 52 120 239 33 22 113 96 116 147 286 113 82 299 256 28 44 205 47 94 263 99 196 35 252 229 177 88 268 162 105 180 234 134 238 2...
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 18312kb
input:
300 299 290 221 29 33 220 213 286 131 96 244 236 279 165 125 98 277 201 217 1 254 119 20 66 77 75 165 285 23 234 241 112 195 240 184 70 201 129 212 256 22 296 94 196 283 156 204 191 178 270 237 1 60 255 62 271 83 188 286 89 287 227 11 263 288 192 124 219 228 235 65 293 277 129 120 88 246 58 65 137 2...
output:
1 1 1 2 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 ...
result:
ok 300 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 15924kb
input:
2 1 1 2 1 2 1 2 2 1
output:
-1 1
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 4ms
memory: 20336kb
input:
300 1 300 289 272 4 18 199 213 133 121 156 132 266 280 222 245 145 124 141 132 254 246 220 200 35 32 140 154 95 77 223 246 94 76 256 272 134 141 184 162 125 146 120 95 58 68 242 250 133 131 235 243 170 176 30 8 261 244 217 220 191 188 260 275 286 269 178 186 75 65 270 277 33 17 220 199 51 37 220 214...
output:
16 9 12 6 6 -1 8 8 13 7 10 4 -1 -1 6 17 4 6 12 3 2 4 7 5 4 5 -1 9 6 1 9 10 8 13 11 1 12 -1 -1 2 3 -1 7 12 1 5 3 13 11 -1 -1 -1 5 8 9 2 2 11 8 10 6 10 1 7 9 6 7 3 -1 4 3 4 5 11 -1 2 7 11 -1 8 8 2 5 5 -1 6 5 6 12 9 2 13 12 5 1 1 6 1 14 2 10 6 -1 10 -1 8 -1 10 9 3 1 5 1 10 6 1 2 12 12 10 8 9 2 11 6 3 1...
result:
ok 300 lines
Test #12:
score: 0
Accepted
time: 0ms
memory: 20260kb
input:
300 299 300 241 245 122 112 274 287 295 287 230 241 278 275 101 108 34 23 14 3 220 229 191 179 250 258 84 78 15 11 164 153 28 19 194 193 236 248 130 142 29 27 158 159 128 138 276 272 99 102 121 111 58 46 140 133 161 169 8 16 192 196 1 13 61 67 269 270 260 258 279 267 25 17 195 182 135 126 247 252 23...
output:
7 3 3 1 1 12 4 2 1 -1 2 -1 1 -1 1 1 1 3 3 1 3 1 -1 3 -1 2 1 9 13 2 2 -1 1 -1 2 3 -1 2 3 6 3 1 2 4 2 2 -1 2 2 1 3 1 1 1 1 2 2 1 3 2 2 2 2 1 13 2 1 2 1 1 3 1 2 4 1 -1 3 1 2 1 1 2 3 3 5 1 1 1 1 1 2 3 1 1 2 1 2 1 2 1 2 1 -1 1 2 3 1 2 1 1 2 2 1 1 2 2 3 1 1 4 1 1 2 1 -1 1 1 2 2 4 1 1 2 4 1 2 1 3 -1 1 13 2...
result:
ok 300 lines
Subtask #2:
score: 8
Accepted
Dependency #1:
100%
Accepted
Test #13:
score: 8
Accepted
time: 6ms
memory: 18856kb
input:
2000 1 1720 615 776 1549 1550 233 1158 818 572 130 1261 711 679 1010 380 206 1185 539 852 692 699 723 667 716 674 251 1140 1818 1821 374 1017 1295 95 1481 1484 272 1119 1641 1644 1315 75 112 1279 1161 229 988 402 1053 337 63 1328 878 512 1778 1780 790 600 1113 277 391 1000 1283 107 1379 11 1985 1986...
output:
1 1095 103 587 -1 275 1270 975 -1 994 845 -1 1429 1270 1 496 934 410 1 299 1342 292 1188 -1 367 1 948 963 541 1001 6 617 570 1 787 217 1372 226 361 622 1 629 362 850 736 246 414 1127 987 449 -1 -1 1089 1506 14 1 424 1225 796 990 1372 1 974 1230 1199 184 1013 1424 1527 856 96 1415 207 757 1 -1 795 11...
result:
ok 2000 lines
Test #14:
score: 0
Accepted
time: 4ms
memory: 20932kb
input:
2000 1 1462 362 493 373 482 53 802 218 637 578 276 718 136 265 590 1503 1506 113 742 636 218 659 195 1416 1417 1209 1210 1529 1530 698 156 467 387 475 379 367 488 1536 1534 244 611 338 517 1244 1246 607 247 1728 1729 439 415 1750 1751 776 78 132 723 93 762 997 998 746 108 1950 1952 837 17 247 608 41...
output:
839 660 1 1162 667 362 773 1 794 788 -1 -1 161 602 1337 374 414 1108 691 1 1202 1 -1 1101 1296 1236 1117 584 692 1 -1 231 -1 -1 -1 600 976 426 1083 1 14 1 324 1 1 52 1036 1087 1 800 1 501 166 1166 57 117 1 1 700 419 398 599 1 641 1243 711 1 130 1 667 629 -1 42 802 406 450 42 718 1 680 1025 887 855 1...
result:
ok 2000 lines
Test #15:
score: 0
Accepted
time: 4ms
memory: 20860kb
input:
2000 1 1435 498 319 1776 1778 639 178 17 801 237 581 379 439 435 382 428 389 1592 1595 303 515 129 689 597 220 919 922 419 398 752 65 43 775 649 168 1323 1324 863 866 504 313 769 48 208 610 1386 1388 65 753 320 498 1929 1932 1251 1253 1680 1683 613 204 662 155 1847 1849 1923 1924 1137 1140 310 508 1...
output:
1177
result:
ok single line: '1177'
Test #16:
score: 0
Accepted
time: 4ms
memory: 20784kb
input:
2000 1654 2000 494 1000 116 68 356 995 4 125 1129 1584 1855 1996 408 394 1808 1156 475 419 646 61 1301 1971 53 131 169 796 963 732 1830 1690 1583 1639 523 771 401 253 776 632 1518 1491 640 365 469 533 1194 1529 1691 1368 1366 1739 255 317 1111 2000 1161 1577 1395 1454 1654 1995 1620 1863 1984 1223 1...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 2000 lines
Test #17:
score: 0
Accepted
time: 10ms
memory: 20844kb
input:
2000 1 1998 712 710 1640 1642 430 428 810 812 666 668 814 816 1776 1774 1716 1714 418 416 1690 1692 484 482 140 142 202 204 900 898 410 412 1292 1294 78 80 408 410 1394 1392 200 198 364 366 1250 1252 866 864 108 110 442 444 1574 1576 1188 1190 950 952 498 500 1960 1958 1774 1776 1286 1288 1644 1642 ...
output:
-1 165 806 281 107 214 303 148 173 179 -1 286 262 -1 99 43 276 119 -1 -1 -1 318 940 150 455 481 -1 849 68 173 234 170 220 310 -1 -1 177 75 96 -1 102 -1 341 368 20 393 105 461 302 342 234 635 268 368 69 -1 450 -1 145 528 -1 2 396 989 230 226 -1 46 20 520 228 -1 553 -1 -1 34 127 3 -1 216 1 292 339 415...
result:
ok 2000 lines
Test #18:
score: 0
Accepted
time: 0ms
memory: 20804kb
input:
2000 1999 2000 1624 1 1711 1 95 2000 253 2000 538 2000 1151 1 488 2000 88 2000 1064 1 28 2000 913 2000 1870 1 930 2000 354 2000 1099 1 1917 1 1104 1 1697 1 1670 1 268 2000 1190 1 298 2000 989 2000 228 2000 1977 1 420 2000 1910 1 1978 1 143 2000 529 2000 285 2000 1479 1 1859 1 366 2000 151 2000 842 2...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 2000 lines
Test #19:
score: 0
Accepted
time: 4ms
memory: 20832kb
input:
1900 938 2000 1870 26 1598 240 1418 884 1553 1776 1061 1200 1781 81 1346 1488 379 395 1533 593 670 513 1693 1813 1746 290 1882 1054 1307 643 911 240 775 525 678 1493 1363 1800 1067 625 1398 1356 1052 294 117 858 479 1429 901 1227 1243 406 332 697 428 887 264 270 612 1824 1831 459 101 388 1346 366 15...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 2000 lines
Test #20:
score: 0
Accepted
time: 3ms
memory: 18772kb
input:
2000 1083 1900 515 1052 1106 1493 1092 1716 613 884 790 613 1629 65 1358 1941 1152 294 22 1626 395 1449 365 1029 699 157 1072 84 1027 587 1492 601 514 24 1785 1933 1008 1828 515 1892 1384 1403 186 587 1183 592 1600 835 1457 1774 1993 835 1222 724 1226 338 1203 1211 883 21 29 1726 1266 407 725 518 14...
output:
2 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 2 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 ...
result:
ok 2000 lines
Test #21:
score: 0
Accepted
time: 3ms
memory: 20784kb
input:
2000 1990 2000 1306 329 1674 1309 1996 1660 1850 437 1404 235 1081 463 1425 1487 96 1082 1347 89 111 319 745 1993 524 1069 1675 533 60 1962 187 682 1131 884 145 996 1241 18 1125 732 728 1155 755 1993 1074 712 674 1193 795 1719 591 1735 442 1441 666 552 1090 254 1250 1161 1018 1881 1752 792 1729 1990...
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 3ms
memory: 20812kb
input:
2000 1999 2000 1682 935 1615 1187 840 158 917 1617 1304 757 192 1414 265 688 1469 1021 1079 920 335 1060 1152 546 1808 382 305 27 1555 83 167 1963 276 1194 1123 1336 1157 1674 1846 693 312 1136 253 1811 1743 699 500 1368 461 1560 1341 134 1987 1161 1617 874 1211 1955 1079 168 147 776 1560 1182 1761 ...
output:
1 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 2 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 ...
result:
ok 2000 lines
Test #23:
score: 0
Accepted
time: 4ms
memory: 18952kb
input:
2000 30 2000 1358 1353 1494 1460 133 130 670 683 192 216 655 639 515 539 153 158 502 492 1508 1510 252 222 311 298 876 894 1259 1243 832 827 866 837 1465 1464 1791 1775 1774 1760 473 468 390 362 1241 1207 1420 1445 817 849 1098 1119 1625 1636 587 559 1544 1540 537 572 711 695 759 753 1227 1199 1728 ...
output:
2 2 66 2 4 36 1 3 36 3 1 13 13 4 2 1 1 5 2 2 1 1 1 21 5 9 44 1 4 19 43 2 32 1 1 6 1 4 30 23 4 1 1 21 22 9 5 41 3 1 3 1 1 2 48 2 28 1 4 1 1 4 32 3 28 5 42 36 1 5 3 5 2 5 45 4 4 1 20 44 -1 4 4 1 2 69 4 2 2 5 39 5 1 1 5 2 2 2 38 1 11 16 1 6 1 2 1 5 1 5 1 36 4 20 5 1 51 4 18 5 4 4 4 5 5 5 4 2 37 2 4 39 ...
result:
ok 2000 lines
Test #24:
score: 0
Accepted
time: 6ms
memory: 20852kb
input:
2000 1999 2000 222 208 1255 1248 58 73 288 291 427 432 221 237 999 991 1667 1676 1623 1627 602 620 328 340 1868 1860 1075 1069 1255 1257 576 584 1168 1163 928 943 1206 1224 1329 1344 640 649 1477 1489 1614 1603 1390 1403 1892 1907 633 615 1898 1894 609 595 787 793 1258 1267 1483 1494 305 304 478 461...
output:
4 4 2 7 -1 11 16 10 -1 7 -1 15 6 16 12 1 7 12 14 1 4 -1 -1 -1 -1 8 11 -1 5 17 15 -1 -1 14 9 1 1 7 14 1 -1 4 5 -1 12 7 6 15 18 2 6 10 10 2 -1 -1 10 21 5 5 4 8 -1 8 4 12 18 7 2 11 2 41 9 6 5 12 11 -1 8 6 3 2 -1 -1 13 7 2 7 -1 10 2 3 10 1 9 16 9 6 6 18 15 18 -1 2 7 8 16 -1 2 9 6 12 7 8 12 6 -1 2 15 18 ...
result:
ok 2000 lines
Subtask #3:
score: 11
Accepted
Test #25:
score: 11
Accepted
time: 380ms
memory: 88432kb
input:
100000 1 81397 1832 1831 52042 85335 73563 63813 61949 75428 37681 99696 99384 37992 94609 42767 1196 1194 56852 80525 71888 65488 58395 78982 67750 69627 65442 71935 79315 58061 48180 89197 61191 76186 84333 53043 66899 70478 71248 66128 52480 84897 52937 84440 83100 54276 46253 91124 18288 18285 4...
output:
31976
result:
ok single line: '31976'
Test #26:
score: 0
Accepted
time: 382ms
memory: 87080kb
input:
100000 1 79526 62602 62605 38796 20170 83633 83634 7929 51038 94832 94835 5314 53653 65508 65510 28844 30123 29986 28980 53957 5009 37153 21813 4738 54229 44138 14828 39394 19572 1361 57606 25437 33530 11300 47667 43949 15017 68053 68055 37314 21652 35235 23731 36727 22239 59830 59832 7807 51160 200...
output:
31404
result:
ok single line: '31404'
Test #27:
score: 0
Accepted
time: 402ms
memory: 87476kb
input:
100000 1 96328 90446 2066 54200 38312 24912 67601 72693 19819 22371 70142 45328 47185 44762 47751 51014 41498 89785 2727 29522 62991 64505 28007 8445 84068 58000 34512 50307 42205 52595 39917 40710 51803 55865 36647 39785 52728 3546 88967 26283 66230 66369 26143 35644 56869 89001 3511 37297 55216 94...
output:
34498
result:
ok single line: '34498'
Test #28:
score: 0
Accepted
time: 358ms
memory: 87604kb
input:
100000 1 74296 70594 70596 95005 95006 99529 99532 25257 23513 14104 34667 36682 12088 20933 27838 42871 5899 22194 26577 88870 88871 9088 39683 81748 81750 14451 34320 24702 24068 64868 64871 22885 25886 26169 22601 69204 69207 25795 22975 11952 36819 425 48346 42593 6177 15845 32926 19514 29257 63...
output:
9534
result:
ok single line: '9534'
Test #29:
score: 0
Accepted
time: 268ms
memory: 88160kb
input:
100000 48691 200000 65657 77347 96237 57738 7545 29253 72902 92423 98076 51329 12009 22806 45467 21798 51575 89191 96844 97011 98981 96565 42682 5275 19443 47374 67533 93549 4651 39900 24863 39660 32637 14176 644 33103 4222 29106 34094 14625 17028 23502 78682 83039 8177 45862 12822 8751 18464 13073 ...
output:
-1
result:
ok single line: '-1'
Test #30:
score: 0
Accepted
time: 384ms
memory: 87848kb
input:
100000 1 199998 646 645 7639 7640 94430 94431 15732 15733 12701 12700 83845 83846 6521 6520 64740 64741 421 422 73945 73944 77112 77111 24166 24167 32891 32892 94870 94871 17911 17910 43154 43155 72867 72866 16240 16239 57099 57098 15459 15460 44070 44069 17987 17986 68699 68700 49461 49460 74077 74...
output:
870
result:
ok single line: '870'
Test #31:
score: 0
Accepted
time: 228ms
memory: 87900kb
input:
100000 99999 199996 98221 1 30724 1 35234 1 45995 1 35816 100000 57337 100000 53911 1 52344 1 98802 1 54268 100000 55087 1 82794 100000 45523 1 10917 100000 17713 1 43527 100000 20630 100000 86698 1 69069 1 9217 100000 3587 100000 55638 1 46980 100000 53234 1 82062 100000 63968 1 25591 1 24446 1 295...
output:
1
result:
ok single line: '1'
Test #32:
score: 0
Accepted
time: 218ms
memory: 86644kb
input:
99000 44632 100000 96411 93783 47245 5318 91891 59938 61851 39951 32578 34139 3934 63316 41754 21700 53135 17113 80663 68943 19052 82396 66307 74991 44295 7130 20107 43800 19803 97966 97191 30555 4839 71955 86324 71808 81945 84480 76771 94321 17209 11362 34180 3266 95481 28504 69706 46660 38945 4502...
output:
1
result:
ok single line: '1'
Test #33:
score: 0
Accepted
time: 226ms
memory: 88552kb
input:
100000 99999 100000 85163 39650 63921 40686 44458 48099 22371 42483 50909 25199 34551 92585 48883 39011 15413 5071 15862 3620 228 47562 4181 92664 85545 49623 94575 78883 56530 88157 96561 49028 29778 77127 91363 46842 36592 58553 40029 30896 66502 71734 76503 67948 31433 71093 55789 2874 14552 3697...
output:
1
result:
ok single line: '1'
Test #34:
score: 0
Accepted
time: 355ms
memory: 87388kb
input:
100000 16 200000 5588 5573 70716 70689 81545 81538 88270 88274 99133 99137 55122 55098 59174 59157 46469 46504 2230 2242 27277 27267 90576 90577 8278 8299 15826 15832 17752 17736 13108 13095 86897 86908 33157 33168 40395 40380 86828 86799 43792 43815 87961 87980 60117 60113 63992 64008 84183 84165 8...
output:
55
result:
ok single line: '55'
Test #35:
score: 0
Accepted
time: 356ms
memory: 88652kb
input:
100000 99999 200000 27954 27973 56245 56264 94273 94271 23338 23339 47494 47505 65351 65340 73341 73359 55219 55204 9610 9627 62425 62408 40954 40944 44587 44582 48837 48817 89837 89856 97566 97551 27218 27229 16539 16554 24970 24969 5249 5239 23809 23820 80661 80665 33402 33384 84185 84171 6838 684...
output:
50
result:
ok single line: '50'
Subtask #4:
score: 25
Accepted
Test #36:
score: 25
Accepted
time: 491ms
memory: 88316kb
input:
100000 99999 78881 26019 31571 64362 64363 26866 30724 48115 9474 97353 97356 44896 12693 6163 51427 49521 8068 10083 47507 1197 56393 39237 18352 43474 14115 73154 73157 16056 41534 94556 94558 8110 49480 46668 10921 18453 39137 67059 67061 6294 51296 41804 15785 28940 28649 96523 96524 42779 14810...
output:
1 12358 1 14581 1 1 1 20605 1 18753 1 1 20777 6771 12441 15794 16147 1 14892 1 14818 17996 1 12753 -1 16598 1 20914 12428 1 1 1 1 -1 1 1 12747 19776 1 1 19285 13118 7774 19883 13245 1 20443 1 15002 1 15051 10951 172 18374 15307 1 15075 1 -1 12816 19674 1 17025 1 11240 1 1 16624 11683 18005 1 14845 1...
result:
ok 50000 lines
Test #37:
score: 0
Accepted
time: 448ms
memory: 86840kb
input:
100000 99999 200000 21936 10603 1694 48378 9832 37447 32492 40902 49222 4283 81950 68487 8087 46147 28472 2516 4664 24937 95849 78298 55060 53536 25934 10979 95794 54383 22729 6572 83160 66825 70125 84583 65712 57625 62245 57068 44155 26547 42301 680 44009 38556 38750 5636 75351 72677 68133 66463 21...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 50000 lines
Test #38:
score: 0
Accepted
time: 637ms
memory: 88196kb
input:
100000 99999 99998 99596 99594 44683 44685 5015 5017 70637 70639 29662 29660 71822 71820 1781 1783 40784 40782 17486 17484 55693 55695 80240 80238 79849 79851 10273 10275 27280 27278 43067 43069 88521 88523 73167 73169 35781 35783 83696 83694 68247 68249 71451 71453 92412 92410 39589 39591 15004 150...
output:
30370 25657 49549 2227 20873 34234 22693 36697 9525 30870 37967 3826 32014 12265 21529 42201 27892 27697 7399 3254 49191 25312 12872 18717 29847 1110 4439 2961 31027 6493 36410 23808 37122 34477 21690 48318 40269 11080 12012 14050 27061 13417 43235 35972 34892 25059 12169 33625 22388 31135 943 1601 ...
result:
ok 50000 lines
Test #39:
score: 0
Accepted
time: 318ms
memory: 87504kb
input:
100000 99999 199996 18512 1 62599 100000 32795 1 72823 100000 40478 1 18978 100000 31922 1 75258 100000 10404 1 32687 1 3123 100000 41926 100000 6553 1 31733 1 42392 100000 21978 100000 83916 100000 48131 100000 51414 1 88104 100000 10367 100000 45105 100000 54914 1 35890 100000 16439 100000 87261 1...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 50000 lines
Test #40:
score: 0
Accepted
time: 316ms
memory: 87412kb
input:
99000 98999 200000 30557 40497 68491 94215 46489 66420 66982 80716 88192 50094 65135 9663 51032 52086 96529 90477 82124 67177 7511 54220 81585 11649 86667 83705 31603 11373 50092 4692 35002 86982 11230 10286 4350 57216 65293 20645 84940 41841 41608 69362 13318 58112 87198 94094 80286 9279 79001 4242...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 49999 lines
Test #41:
score: 0
Accepted
time: 337ms
memory: 88408kb
input:
100000 99999 199000 31171 93683 72809 15657 92267 50996 87683 1736 40118 87886 90337 42355 64838 74586 15035 66253 2224 15363 42598 39819 60351 32137 66706 25726 57355 3078 59595 8121 31701 18060 92713 47116 6465 13901 4508 81856 23208 34514 41496 83727 36592 8676 67324 50894 31239 32453 56304 22306...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 50000 lines
Test #42:
score: 0
Accepted
time: 484ms
memory: 86876kb
input:
100000 99999 200000 12983 12978 46313 46312 18563 18553 8 7 51468 51467 82379 82375 62334 62324 79439 79444 93302 93315 6684 6682 53576 53572 44779 44771 62141 62154 13773 13786 82917 82902 715 727 71745 71736 18738 18741 87362 87375 25172 25177 42513 42509 31847 31852 79043 79052 19842 19856 401 39...
output:
163 191 1 117 437 186 53 76 393 131 556 54 67 102 296 101 113 201 142 36 230 172 79 23 171 143 84 258 249 235 44 104 147 273 192 94 279 324 170 286 110 35 23 331 217 30 257 114 311 159 35 294 6 43 382 324 15 216 136 562 2 195 73 9 35 59 103 12 162 15 38 186 2 145 6 197 8 116 58 194 541 46 510 290 44...
result:
ok 50000 lines
Test #43:
score: 0
Accepted
time: 494ms
memory: 87352kb
input:
100000 99999 200000 57595 57582 30805 30785 46992 47018 22268 22250 98306 98277 46039 46050 81592 81605 69569 69558 87615 87631 93878 93880 53834 53814 55079 55106 45219 45209 11781 11807 83181 83186 92187 92167 44644 44629 38256 38246 36893 36899 50748 50751 70859 70861 24049 24029 2510 2494 7903 7...
output:
1549 3351 1938 1052 2936 2653 901 1775 191 253 1920 968 1936 1032 2639 3756 478 1069 2839 2355 555 732 1871 2655 1046 2706 3318 243 4106 2513 896 588 3389 304 1695 603 1230 371 3484 3746 1069 1671 3572 2042 3730 4087 2596 3577 3731 1158 3855 2514 225 1656 1109 1583 183 1205 1025 2287 3033 918 3213 1...
result:
ok 50000 lines
Subtask #5:
score: 35
Accepted
Test #44:
score: 35
Accepted
time: 520ms
memory: 88056kb
input:
100000 22064 200000 303 15995 58467 79850 4244 40609 35993 44061 68252 76712 77601 83217 54023 88464 73305 88555 51728 89955 57527 89549 4590 37615 43565 44051 72102 72192 12597 39113 50902 90961 54855 65292 61740 71227 73485 88925 16017 38911 63493 69058 7630 21091 27807 49468 13032 32590 54228 952...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 50000 lines
Test #45:
score: 0
Accepted
time: 734ms
memory: 86944kb
input:
100000 1 99999 38995 38996 27027 27028 27695 27696 84189 84190 84987 84988 49640 49641 14363 14364 10196 10197 53910 53911 81171 81172 1881 1882 50266 50267 43714 43715 58211 58212 87100 87101 50482 50483 5081 5082 84816 84817 8252 8253 51842 51843 71287 71288 35861 35862 13344 13345 78334 78335 502...
output:
64345 18291 12464 65634 70785 64113 4763 34041 43475 10538 8020 64745 2113 59238 54602 75286 11779 85417 26159 80028 60597 66078 95954 5151 24438 5795 11064 3004 31587 10569 33172 28256 48359 93005 12148 81991 29793 56720 38477 70826 75314 6932 66649 3361 54211 53698 52984 81589 44572 36494 10088 62...
result:
ok 50000 lines
Test #46:
score: 0
Accepted
time: 690ms
memory: 88392kb
input:
100000 2 49999 64858 64860 1290 1292 55736 55738 52288 52290 46600 46602 39192 39194 98264 98266 20970 20972 32796 32798 51382 51384 55294 55296 71178 71180 95310 95312 28392 28394 62146 62148 36588 36590 48584 48586 84936 84938 19266 19268 45986 45988 67508 67510 93270 93272 34746 34748 53868 53870...
output:
15595 31875 7634 6529 10754 15469 33681 31824 7495 38502 16348 35382 24462 36431 28472 31661 14304 7404 30305 5777 6469 29726 7687 32616 42425 1728 16788 18703 12317 14296 13179 35558 45882 20165 33746 35424 36147 5958 26894 23318 23260 45721 28729 25039 4367 1649 7512 13061 40605 11075 30226 24724 ...
result:
ok 50000 lines
Test #47:
score: 0
Accepted
time: 631ms
memory: 87640kb
input:
100000 5 19999 39722 39727 97337 97342 53182 53187 80672 80677 35372 35377 97207 97212 12522 12527 7117 7122 55987 55992 73362 73367 52622 52627 6592 6597 74367 74372 62982 62987 73932 73937 93342 93347 47147 47152 15797 15802 24572 24577 10182 10187 50627 50632 35652 35657 57022 57027 40867 40872 9...
output:
7212 8957 543 19231 13340 2958 8499 6569 5525 1252 10415 6283 14331 9856 13758 3391 138 7967 10264 2591 9671 9140 9596 13288 11761 10484 5535 16661 12249 2208 5066 2690 3330 8634 11707 16998 10439 13215 3069 14055 10595 3050 11146 2401 2704 14861 12296 2772 11396 13553 5916 8469 2540 1840 5214 7050 ...
result:
ok 50000 lines
Test #48:
score: 0
Accepted
time: 543ms
memory: 88320kb
input:
100000 8 4999 37092 37112 59832 59852 52812 52832 72412 72432 18552 18572 8192 8212 94272 94292 20412 20432 41832 41852 81872 81892 59692 59712 66872 66892 26852 26872 98812 98832 5472 5492 3432 3452 1892 1912 6912 6932 9732 9752 66472 66492 97792 97812 53592 53612 9452 9472 80672 80692 17332 17352 ...
output:
3860 727 3639 2481 943 4222 3261 -1 4522 2499 1988 4278 48 2875 3111 3640 577 2540 4758 429 4686 -1 4276 1926 174 2117 667 2956 4368 4801 -1 -1 116 3098 2525 1822 4628 1559 3699 -1 4137 -1 42 -1 4516 3365 1096 2520 1176 1879 4323 4237 2921 2930 2131 2333 928 3172 2651 1324 1953 161 1403 3946 1414 36...
result:
ok 50000 lines
Test #49:
score: 0
Accepted
time: 496ms
memory: 86984kb
input:
100000 98 999 3125 3225 21525 21625 44925 45025 10225 10325 60825 60925 91925 92025 41925 42025 31625 31725 10025 10125 72625 72725 89425 89525 125 225 10725 10825 91125 91225 20225 20325 72525 72625 66025 66125 30325 30425 39625 39725 13225 13325 7225 7325 69025 69125 67225 67325 16925 17025 20525 ...
output:
120 330 491 760 674 761 399 491 905 220 345 258 291 195 781 420 753 499 742 515 37 454 439 162 630 721 979 645 934 454 880 103 105 916 349 35 579 145 836 926 806 118 412 447 400 895 938 375 226 580 489 15 838 3 234 846 338 384 766 644 106 895 111 345 849 502 23 624 344 966 268 549 933 63 681 164 578...
result:
ok 50000 lines
Test #50:
score: 0
Accepted
time: 390ms
memory: 88064kb
input:
100000 99999 99999 82197 100000 28905 100000 29254 100000 76042 100000 73219 100000 48314 100000 44299 100000 4077 100000 71091 100000 14780 100000 23182 100000 24731 100000 1213 100000 54074 100000 55866 100000 6601 100000 41573 100000 20160 100000 7873 100000 35293 100000 62680 100000 32899 100000...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 50000 lines
Test #51:
score: 0
Accepted
time: 0ms
memory: 22380kb
input:
300 119 300 91 106 24 236 268 281 113 117 125 141 270 285 106 175 100 155 32 112 67 277 157 219 50 179 18 248 100 179 69 199 214 279 143 182 25 56 172 286 109 281 5 8 199 298 81 117 141 282 156 258 150 298 15 26 55 59 4 108 12 201 30 65 97 261 65 173 59 237 73 206 2 173 152 270 91 207 45 105 166 291...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 300 lines
Test #52:
score: 0
Accepted
time: 0ms
memory: 18832kb
input:
2000 1924 2000 859 1838 225 1292 221 1896 199 863 853 1703 732 1408 440 588 1492 1694 1473 1700 456 768 72 574 1193 1885 96 97 582 1284 408 1542 1064 1804 8 1795 358 621 785 1657 1564 1696 455 527 1372 1801 863 1421 367 1464 814 1673 1034 1535 5 648 231 1580 592 1171 1008 1468 479 624 361 1373 327 3...
output:
2 1 1 1 1 2 2 1 2 1 1 2 1 1 2 1 1 1 2 2 1 2 2 1 1 2 1 1 1 1 1 2 1 2 2 1 2 2 2 2 2 1 2 2 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 2 1 1 2 1 1 1 1 2 2 1 1 1 1 1 1 1 2 1 2 1 2 1 1 1 2 1 2 1 2 1 1 1 2 2 2 1 1 1 1 1 2 1 1 1 1 1 2 2 1 2 1 2 1 1 2 1 1 2 1 2 1 1 1 2 1 2 1 2 1 1 1 1 1 2 2 1 ...
result:
ok 2000 lines
Test #53:
score: 0
Accepted
time: 336ms
memory: 88252kb
input:
100000 22700 200000 32780 39621 85150 91341 60742 62346 28416 67870 28628 97868 57127 74428 26359 47905 57695 68033 83929 97050 40844 66968 734 16211 19190 98379 71990 78443 81776 96477 27237 46029 30926 83485 36131 63720 27238 33678 33862 63102 3035 27864 2242 43294 21291 65473 7608 34475 52921 927...
output:
1
result:
ok single line: '1'
Test #54:
score: 0
Accepted
time: 376ms
memory: 88440kb
input:
100000 99999 200000 22649 52656 33196 92961 60551 65931 51967 66254 47751 80827 52451 94116 39724 60525 56588 77431 6670 31106 2156 3501 24638 34100 59984 73505 78880 79127 17538 46611 12841 51091 43772 55670 42876 47251 8195 81336 15716 23988 47326 48963 25878 97013 56809 63926 12645 49722 61119 93...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 50000 lines
Test #55:
score: 0
Accepted
time: 397ms
memory: 86512kb
input:
99000 18855 200000 36150 36660 25171 34635 18407 39670 9930 29844 70506 94929 73038 93666 81547 91178 62590 89918 28713 59320 13834 23349 17569 51022 49833 49961 16293 50490 19978 24476 54115 60004 5760 89440 54008 76698 48768 86188 26973 83487 27036 78771 57905 80114 71156 96266 115 53925 48156 528...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 49999 lines
Test #56:
score: 0
Accepted
time: 424ms
memory: 87092kb
input:
100000 61580 199000 56555 99750 45204 89733 28010 83277 53730 98369 78780 95402 5820 41750 16251 34243 40340 50293 17864 71036 78481 86983 2355 20103 33165 45588 26585 60323 55419 95587 15130 49151 20531 48708 11015 12925 63307 66838 47331 77499 54542 64625 50038 51594 636 27250 67627 99756 82345 83...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 50000 lines
Test #57:
score: 0
Accepted
time: 0ms
memory: 24388kb
input:
300 3 300 285 289 116 118 124 131 19 21 295 297 122 126 160 163 5 9 178 183 207 208 95 102 210 217 221 224 4 7 83 85 174 176 285 290 237 238 162 166 242 244 90 91 92 94 107 114 155 156 205 207 87 88 219 225 24 29 169 175 217 218 171 177 204 206 76 83 221 222 121 126 73 75 106 109 253 258 20 22 27 32...
output:
25 23 9 20 8 5 11 4 17 -1 13 10 3 12 13 16 22 21 1 15 24 20 1 5 10 4 5 14 27 15 15 10 24 28 5 13 11 27 17 25 28 6 13 28 13 -1 25 12 14 11 21 18 14 5 27 21 23 18 23 1 -1 19 14 -1 23 27 3 1 27 20 1 3 8 8 22 5 9 13 22 8 4 -1 19 4 1 22 7 14 13 6 11 8 16 1 5 22 20 17 22 6 1 24 28 8 24 2 27 24 7 -1 6 1 26...
result:
ok 300 lines
Test #58:
score: 0
Accepted
time: 4ms
memory: 18860kb
input:
2000 5 2000 784 794 194 196 1140 1146 27 38 379 381 1218 1225 531 535 201 214 1172 1176 61 72 1926 1941 1930 1931 357 368 975 990 178 179 1055 1069 1841 1851 1396 1401 1191 1200 498 513 96 107 355 369 404 418 1808 1819 1446 1452 1364 1376 1134 1147 738 752 561 569 1259 1271 863 872 1546 1553 1835 18...
output:
30 26 13 16 11 45 101 33 13 67 2 15 13 57 38 27 40 71 5 11 45 15 2 44 89 15 2 15 93 120 44 70 53 11 37 31 2 11 17 119 46 89 133 81 107 29 23 70 76 29 18 25 -1 6 100 2 100 109 55 100 5 45 3 28 27 46 97 41 9 96 15 97 111 23 28 35 38 151 27 31 16 6 87 5 19 135 41 3 28 123 124 127 11 20 103 160 43 24 11...
result:
ok 2000 lines
Test #59:
score: 0
Accepted
time: 375ms
memory: 86772kb
input:
100000 2 200000 97222 97228 1829 1830 65364 65369 57787 57796 23123 23124 6571 6573 12354 12360 47629 47637 17276 17286 28387 28392 10743 10744 98000 98001 24250 24251 17565 17575 42139 42147 53770 53776 86351 86353 7973 7977 85530 85537 47639 47648 37017 37025 95220 95230 10729 10731 97429 97433 63...
output:
68
result:
ok single line: '68'
Test #60:
score: 0
Accepted
time: 679ms
memory: 87684kb
input:
100000 99999 200000 21268 21278 27445 27449 44968 44978 94671 94678 45305 45312 28055 28057 84084 84099 28127 28139 84220 84232 16938 16951 34118 34132 7940 7951 2237 2248 70060 70075 64516 64519 53609 53619 73739 73742 60438 60444 89813 89816 27903 27909 75414 75423 41827 41828 32944 32953 80621 80...
output:
2008 6553 3101 1476 1908 5241 2357 2214 4673 5385 3827 7600 971 2387 6122 5654 55 292 2753 2986 4153 1575 28 5950 5548 4159 5074 6755 3052 2811 6895 4506 7595 3441 7656 5542 2487 318 2885 2586 5952 4319 787 129 4421 3959 4667 837 5789 819 1866 6921 4672 7233 4219 2660 4867 1024 2866 6767 1079 217 14...
result:
ok 50000 lines
Test #61:
score: 0
Accepted
time: 607ms
memory: 87924kb
input:
100000 11 200000 33041 33049 27650 27668 23963 23980 37966 37969 65126 65140 91421 91431 58508 58528 5026 5031 218 237 4783 4792 46120 46133 34734 34736 38965 38982 67411 67427 43652 43665 76264 76284 32159 32163 42278 42289 68775 68782 13916 13932 16699 16710 94330 94333 22869 22889 99856 99867 351...
output:
3700 3369 1986 2732 4106 457 1189 4076 2170 1280 658 439 168 2558 861 2479 940 385 2215 1583 4477 1961 3857 3824 139 5030 4299 5341 2333 64 3658 2080 583 5254 919 2453 4684 1465 4628 4490 2042 2555 2379 1497 2181 1216 3062 4408 4464 1835 4151 5538 3587 1903 789 291 2760 1207 1642 2721 1283 5502 1119...
result:
ok 50000 lines
Test #62:
score: 0
Accepted
time: 555ms
memory: 88320kb
input:
100000 8 200000 99601 99622 58462 58476 77185 77188 89570 89577 41146 41147 49069 49071 60149 60163 51642 51645 82302 82311 44198 44227 31440 31447 2601 2621 22521 22530 62230 62237 63234 63239 48482 48502 14015 14041 5669 5675 6823 6836 50174 50187 69649 69668 43707 43730 48531 48536 60259 60274 72...
output:
486 698 1301 3414 1512 3162 360 2749 1502 2195 2033 3250 2817 329 3532 1605 2342 3342 2622 565 770 3076 410 273 2199 824 3413 866 460 2043 659 1670 281 403 2176 440 3672 3545 2630 1530 2176 2017 3039 2717 520 644 3423 3229 1981 524 3803 1454 1702 2143 2697 2600 1394 2169 1809 582 2279 288 2139 2260 ...
result:
ok 50000 lines
Subtask #6:
score: 13
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #63:
score: 13
Accepted
time: 642ms
memory: 88360kb
input:
100000 1 71635 86571 70420 68084 88908 72824 84168 61492 95500 80674 76317 5319 5316 83999 72992 88246 68745 78318 78674 99551 57440 95872 61119 69701 87291 50613 50610 53037 53034 46909 46906 78479 78513 90651 66340 62862 94130 84873 72118 3456 3453 51295 51294 53130 53128 64475 92517 93971 63020 9...
output:
49317 1 1 18700 3492 -1 11224 52398 54236 35831 -1 45060 1 6039 -1 1008 1 1 8972 65396 60328 8577 53819 56573 -1 1 1 -1 55963 2790 37817 65407 60577 1 61786 3940 56905 38446 -1 1 38961 1 15981 50355 5421 57642 1 1 -1 62955 39143 37847 1 1 3290 16178 48079 13113 52447 1357 29987 37175 28833 -1 50919 ...
result:
ok 50000 lines
Test #64:
score: 0
Accepted
time: 730ms
memory: 87280kb
input:
100000 1 89406 91415 29877 5717 5714 69778 51514 19114 19113 67267 54025 66753 54539 42786 78507 33015 88278 48502 72791 11138 11137 39321 81972 86422 34870 13354 13351 38128 83165 84095 37197 62233 59059 9438 9436 55328 65965 67142 54150 84075 37217 67453 53839 2838 2837 4675 4673 13452 13449 67191...
output:
67901 32431 39003 77808 54000 44301 57359 -1 63974 38450 58751 76519 18365 1 77598 623 8498 27641 7943 51057 75682 54972 1 76186 80764 1 20665 -1 22324 40409 70429 68233 1 18706 31034 66084 82193 40570 74452 26183 59893 73515 1 56460 47288 73935 25279 41408 39880 73509 53510 33647 21547 59287 -1 589...
result:
ok 50000 lines
Test #65:
score: 0
Accepted
time: 654ms
memory: 88020kb
input:
100000 1 75033 56084 94018 67611 82491 27256 27253 16 14 74150 75952 3357 3356 76497 73604 17491 17490 72622 77480 74361 75741 39169 39167 62610 87492 72993 77109 52296 97806 68090 82012 79784 70317 78239 71862 31166 31163 58148 91954 55996 94106 81552 68549 78236 71865 58326 91776 41521 41520 75559...
output:
1 68333 41333 63075 42053 41581 2264 -1 63917 1 40109 27597 16005 50884 35534 61213 49977 38399 12541 1 1 1 2171 14263 5638 62938 1 30575 1 60430 34571 60913 32852 1924 68624 37984 19538 41532 22390 1 62894 5128 53327 42601 42409 41745 9823 -1 4850 40527 -1 13766 37537 1 12829 11491 37243 68094 6898...
result:
ok 50000 lines
Test #66:
score: 0
Accepted
time: 292ms
memory: 86648kb
input:
100000 93363 200000 41731 27710 75233 58435 71331 70083 15519 15567 82835 50696 4015 31519 74281 77084 21936 1149 98996 88100 12468 22298 84892 78372 16283 41869 88093 93267 46342 42896 27591 3102 86735 99857 25014 47149 26399 45143 5345 28310 81374 99212 29428 17764 28342 33343 94817 77811 82236 78...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 50000 lines
Test #67:
score: 0
Accepted
time: 595ms
memory: 87328kb
input:
100000 1 199998 19250 19251 94225 94224 43773 43774 17138 17139 75432 75431 42034 42033 40893 40894 57289 57290 47788 47789 83637 83636 39675 39674 74241 74242 36521 36520 83364 83363 4962 4963 33096 33095 65849 65850 84316 84317 57674 57675 78704 78703 69895 69894 13496 13497 83965 83966 36747 3674...
output:
22353 71038 37802 35308 45213 6460 5043 7061 15628 99079 43177 67953 54595 41557 76529 12685 7930 36650 48473 69016 3764 47939 77034 20117 71763 7695 68816 16854 55040 29021 1193 27106 68145 32247 67216 41540 26222 37382 30526 91580 43572 34165 55998 39926 35628 61775 25691 35552 9633 68882 80089 50...
result:
ok 50000 lines
Test #68:
score: 0
Accepted
time: 421ms
memory: 86652kb
input:
99000 6874 200000 90353 83830 53917 90875 36696 60975 25920 67083 83408 85733 43130 94462 55348 95591 58776 95342 44458 21211 85411 19619 52408 31838 11122 61004 41990 80182 64545 6062 87694 69884 22909 9350 69728 17443 90304 9670 57465 97146 70043 61745 83196 18209 71731 17194 14436 53244 94151 421...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 50000 lines
Test #69:
score: 0
Accepted
time: 337ms
memory: 88084kb
input:
100000 55281 199000 24953 48599 66699 13092 81867 75622 94645 50911 77341 93141 7488 49608 3377 38456 82228 55806 93648 7699 83982 88385 42280 88251 86819 78743 76561 75478 14489 71277 54115 88726 60795 26355 72810 47756 30883 13971 15502 39722 38873 97411 73921 63455 29293 95622 43062 15732 36338 8...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 50000 lines
Test #70:
score: 0
Accepted
time: 527ms
memory: 87568kb
input:
100000 2 200000 2340 2336 7987 7973 90947 90933 87998 88010 22148 22137 99740 99741 43523 43535 75120 75108 90637 90639 46811 46812 12772 12762 29697 29683 63016 63014 45614 45627 5599 5610 30507 30517 65278 65286 36553 36547 54065 54072 11426 11431 68703 68693 16896 16907 69391 69377 16719 16709 92...
output:
-1 27 709 453 246 -1 -1 80 805 -1 -1 459 -1 -1 -1 963 512 -1 -1 -1 98 -1 -1 -1 259 1408 1034 -1 36 -1 -1 -1 934 -1 -1 -1 -1 -1 -1 -1 918 34 68 -1 1227 -1 839 -1 167 -1 1146 514 -1 -1 -1 -1 -1 -1 899 -1 -1 479 -1 432 -1 -1 -1 651 507 -1 1851 -1 -1 -1 775 988 -1 -1 445 311 -1 -1 -1 7 -1 -1 -1 -1 -1 -1...
result:
ok 50000 lines
Test #71:
score: 0
Accepted
time: 623ms
memory: 87128kb
input:
100000 34 200000 89568 89535 91833 91834 22270 22307 85103 85095 34420 34389 36631 36605 13600 13597 24098 24082 78419 78456 41376 41382 73717 73706 73905 73913 38775 38792 28828 28827 7812 7841 19498 19463 32662 32692 75449 75472 43066 43095 18575 18545 23865 23850 82377 82337 82975 82979 42541 425...
output:
148 302 1923 1908 398 1321 1166 1022 1493 567 91 1072 1336 330 1525 1193 1136 654 849 1252 2694 463 173 1551 619 1925 1886 1153 982 1843 477 157 479 123 2102 2064 831 101 514 887 861 1040 936 2051 2261 868 1108 1184 1281 1439 1727 977 1981 903 360 1516 466 2278 85 1269 360 398 1401 775 2755 277 130 ...
result:
ok 50000 lines
Extra Test:
score: 0
Extra Test Passed