QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #330775 | #4083. 아이싱 | hotboy2703 | 150 ✓ | 215ms | 56576kb | C++14 | 1.8kb | 2024-02-17 18:55:57 | 2024-02-17 18:55:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
mt19937_64 rng(69420);//chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l,ll r){
return rng()%(r-l+1)+l;
}
namespace{
const ll MAXN=2.5e5;
vector <ll> g[MAXN+100];
ll in[MAXN+100];
map <ll,ll> mp;
ll depth[MAXN+100];
bool color[MAXN+100];
ll dp[MAXN+100];
ll target;
ll bad_edge = 0;
void dfs(ll u,ll p){
in[u] = 1;
for (auto v:g[u]){
if (v==p)continue;
if (in[v]){
if (depth[v] < depth[u]){
ll tmp = random(1,MASK(60)-1);
dp[v] ^= tmp;
dp[u] ^= tmp;
if (color[u] == color[v]){
target ^= tmp;
bad_edge++;
}
mp[tmp]++;
}
}
else{
depth[v] = depth[u] + 1;
color[v] = 1-color[u];
dfs(v,u);
dp[u] ^= dp[v];
}
}
mp[dp[u]]++;
}
}
long long count_ways(int N, std::vector<int> U, std::vector<int> V) {
for (ll i = 0;i < sz(U);i ++){
g[U[i]].push_back(V[i]);
g[V[i]].push_back(U[i]);
}
dfs(1,1);
if (target==0)return 1;
ll res1 = mp[target];
if (res1)return res1;
ll res2=0;
for (auto x:mp){
if (mp.find(target^x.fi) != mp.end())res2+=mp[target^x.fi]*x.se;
}
res2=res2/2;
return res2;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 9644kb
input:
3 2 1 2 2 3
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 9472kb
input:
4 6 1 2 1 3 1 4 2 3 2 4 3 4
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 9400kb
input:
5 9 1 2 1 3 1 4 2 3 2 4 2 5 3 4 3 5 4 5
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 9468kb
input:
12 16 1 2 2 3 3 4 4 1 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 5 1 5 2 7 3 9 4 11
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 9700kb
input:
3 3 1 2 2 3 3 1
output:
3
result:
ok single line: '3'
Test #6:
score: 0
Accepted
time: 0ms
memory: 9452kb
input:
6 9 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 3ms
memory: 9616kb
input:
13 16 2 8 10 11 3 10 2 3 5 9 9 11 2 6 4 7 1 3 5 6 4 10 1 6 8 13 11 12 8 12 6 13
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 3ms
memory: 9472kb
input:
4 3 3 4 2 3 1 2
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 9700kb
input:
4 5 3 4 1 2 1 3 2 4 1 4
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 3ms
memory: 9684kb
input:
32 53 28 29 17 32 17 23 11 32 7 16 21 29 19 20 6 22 1 8 13 26 13 24 18 27 4 11 3 31 7 25 6 21 20 32 6 28 12 26 10 15 11 29 3 20 6 20 4 20 21 23 4 17 17 29 20 23 22 29 11 23 3 17 2 12 10 25 5 19 10 11 3 28 14 26 12 19 8 12 6 17 4 22 20 29 4 28 1 30 23 28 23 31 6 11 22 32 9 30 27 30 21 32 4 21 9 15
output:
9
result:
ok single line: '9'
Test #11:
score: 0
Accepted
time: 0ms
memory: 9428kb
input:
4 4 2 4 1 3 1 2 1 4
output:
3
result:
ok single line: '3'
Test #12:
score: 0
Accepted
time: 4ms
memory: 9500kb
input:
100 104 16 80 80 91 4 91 16 4 6 47 16 77 36 47 36 34 67 34 35 67 35 92 92 42 42 74 44 74 98 44 98 77 37 23 33 80 22 37 79 22 100 79 100 10 90 10 90 28 28 81 94 81 94 88 88 33 49 83 91 45 83 53 53 13 13 63 75 63 18 75 18 68 68 99 99 46 54 46 54 45 24 40 4 12 5 24 5 93 96 93 96 84 11 84 11 48 48 1 1 8...
output:
288
result:
ok single line: '288'
Test #13:
score: 0
Accepted
time: 0ms
memory: 9644kb
input:
190 194 98 137 134 137 174 134 174 98 76 84 77 98 114 84 114 157 157 182 182 24 78 24 187 78 187 117 117 67 67 149 149 163 8 163 8 125 167 125 165 167 38 165 38 56 56 17 63 17 85 63 85 77 54 102 137 96 36 102 43 36 113 43 113 21 12 21 146 12 146 170 91 170 42 91 185 42 185 173 158 173 150 158 87 150...
output:
968
result:
ok single line: '968'
Test #14:
score: 0
Accepted
time: 0ms
memory: 9504kb
input:
100 101 6 16 23 80 49 6 16 1 49 91 40 91 4 40 4 47 36 47 34 36 34 67 67 35 35 92 42 92 74 42 74 44 98 44 98 77 37 77 22 37 79 22 79 100 10 100 10 90 90 28 81 28 81 94 94 88 88 33 83 33 83 53 53 13 13 63 75 63 18 75 18 68 68 99 99 46 54 46 54 45 24 45 5 24 93 5 93 96 84 96 84 11 48 11 48 1 23 86 17 8...
output:
2209
result:
ok single line: '2209'
Test #15:
score: 0
Accepted
time: 3ms
memory: 9480kb
input:
190 191 76 98 137 54 89 76 93 98 89 134 134 97 174 97 174 84 84 114 114 157 182 157 24 182 24 78 78 187 187 117 117 67 149 67 149 163 8 163 125 8 167 125 167 165 165 38 56 38 17 56 17 63 63 85 77 85 102 77 36 102 43 36 43 113 21 113 12 21 12 146 170 146 91 170 42 91 42 185 173 185 158 173 150 158 87...
output:
8649
result:
ok single line: '8649'
Test #16:
score: 0
Accepted
time: 0ms
memory: 9496kb
input:
100 200 76 88 92 76 100 92 100 77 75 77 85 75 85 6 31 6 31 95 88 53 62 53 76 62 62 15 92 15 41 15 41 100 41 72 72 77 19 72 75 19 19 42 85 42 39 42 6 39 23 39 31 23 23 97 95 97 28 53 28 84 62 84 84 24 15 24 43 24 41 43 14 43 72 14 33 14 33 19 49 33 49 42 1 49 1 39 99 1 23 99 99 57 57 97 61 28 61 74 8...
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 0ms
memory: 9444kb
input:
100 200 95 30 47 30 87 47 87 58 58 42 91 42 71 91 71 16 16 39 25 39 100 25 100 9 9 22 22 2 2 50 50 65 85 65 82 85 33 82 79 33 45 79 45 56 56 55 86 55 86 69 69 51 18 51 48 18 48 96 96 64 94 64 94 89 4 89 61 4 61 93 44 93 44 67 53 67 53 66 66 13 13 37 27 37 27 15 52 15 92 52 92 81 99 81 7 99 1 7 1 14 ...
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 3ms
memory: 9692kb
input:
20 102 10 17 12 17 12 4 4 3 2 3 6 2 20 6 5 20 1 5 15 1 15 14 13 14 18 13 18 7 8 7 8 19 16 19 11 16 11 9 5 10 16 1 10 1 4 15 18 6 7 17 9 10 10 20 14 19 12 8 12 9 6 1 18 15 19 18 19 1 1 12 10 2 5 14 6 17 13 8 10 8 5 18 9 19 15 9 13 20 13 1 16 3 2 12 19 4 15 16 16 5 1 3 11 17 11 18 6 14 2 19 9 3 4 6 10...
output:
1
result:
ok single line: '1'
Subtask #2:
score: 23
Accepted
Dependency #1:
100%
Accepted
Test #19:
score: 23
Accepted
time: 3ms
memory: 9488kb
input:
490 494 447 358 88 447 249 88 249 358 169 428 358 167 169 439 372 439 372 385 385 31 31 73 73 417 401 417 253 401 342 253 342 280 142 280 321 142 426 321 81 426 81 48 48 35 35 86 156 86 156 66 66 130 130 274 274 311 472 311 63 472 63 479 479 67 67 443 443 136 136 157 157 18 18 179 179 7 7 285 80 285...
output:
7200
result:
ok single line: '7200'
Test #20:
score: 0
Accepted
time: 0ms
memory: 9484kb
input:
490 491 358 428 447 288 377 428 462 358 88 377 170 88 170 249 169 249 169 439 439 372 372 385 385 31 73 31 417 73 401 417 401 253 342 253 280 342 142 280 321 142 321 426 426 81 81 48 35 48 35 86 86 156 156 66 66 130 274 130 311 274 311 472 472 63 63 479 479 67 67 443 443 136 136 157 157 18 18 179 7 ...
output:
59049
result:
ok single line: '59049'
Test #21:
score: 0
Accepted
time: 5ms
memory: 9992kb
input:
500 5000 92 337 337 295 150 295 150 55 55 83 83 433 200 433 200 347 347 271 350 271 350 484 484 105 105 382 382 228 228 153 309 153 309 293 425 293 425 128 128 211 47 211 47 385 27 385 27 335 93 335 464 93 70 464 70 266 266 102 102 156 156 4 4 494 373 494 373 213 213 242 157 242 60 157 60 441 257 44...
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 3ms
memory: 9572kb
input:
1000 999 937 938 606 607 767 768 235 236 827 828 894 895 901 902 349 350 217 218 63 64 947 948 128 129 657 658 108 109 253 254 535 536 321 322 261 262 78 79 590 591 625 626 115 116 244 245 610 611 760 761 378 379 268 269 283 284 10 11 596 597 440 441 493 494 107 108 918 919 130 131 621 622 144 145 4...
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 3ms
memory: 9576kb
input:
1000 999 119 296 688 168 975 848 264 196 488 866 302 56 525 224 983 731 761 476 825 334 840 908 496 697 71 964 877 138 171 426 799 792 861 337 515 368 66 70 825 365 205 55 768 66 17 276 118 415 620 930 166 860 879 155 817 1 495 405 359 579 121 485 961 742 916 704 859 135 302 894 291 97 389 942 618 4...
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 9560kb
input:
1000 999 680 809 34 44 243 877 355 589 273 691 458 643 193 464 198 632 478 570 320 457 309 866 636 721 181 475 278 565 567 616 138 490 335 554 293 663 246 769 765 769 148 694 384 406 689 712 84 879 268 418 239 806 376 827 247 862 576 848 309 926 140 886 750 989 240 701 347 599 227 599 369 441 187 39...
output:
1
result:
ok single line: '1'
Test #25:
score: 0
Accepted
time: 0ms
memory: 9572kb
input:
1000 1176 133 835 227 953 33 449 196 934 171 587 659 790 256 605 72 393 438 601 599 922 177 221 28 84 156 782 17 48 49 302 198 613 142 154 156 601 788 898 295 431 714 982 374 990 394 539 45 837 73 340 203 371 46 239 159 621 26 424 193 249 623 777 43 184 257 308 582 994 419 420 237 895 373 963 206 58...
output:
6
result:
ok single line: '6'
Test #26:
score: 0
Accepted
time: 3ms
memory: 9748kb
input:
1000 1032 593 809 799 834 878 896 154 226 625 931 92 334 9 812 878 348 817 948 335 874 38 215 331 978 306 997 614 573 661 614 459 38 6 625 220 364 145 682 435 876 891 601 200 244 228 407 743 915 28 612 174 372 579 730 313 347 445 717 702 836 938 983 655 704 955 981 272 988 123 332 165 305 866 939 14...
output:
422
result:
ok single line: '422'
Test #27:
score: 0
Accepted
time: 2ms
memory: 10320kb
input:
4900 4904 4396 4471 4396 2987 4016 2987 4016 4471 4265 4192 4471 4757 3026 4192 3965 3026 3965 2851 2851 3244 3244 4583 922 4583 922 160 160 915 2416 915 2416 4406 4406 1279 4389 1279 1252 4389 4185 1252 4185 1055 2997 1055 3210 2997 4862 3210 4862 1880 1880 4217 1521 4217 1521 2964 4303 2964 4303 2...
output:
749088
result:
ok single line: '749088'
Test #28:
score: 0
Accepted
time: 0ms
memory: 10300kb
input:
4900 5000 1814 2573 2573 1336 369 1336 1814 369 1758 2511 1177 1814 2511 409 4320 409 3986 4320 1728 3986 1728 1375 4449 1375 4449 1007 1007 2519 2519 1723 1199 1723 1199 3445 3445 2058 1859 2058 173 1859 2172 173 4133 2172 888 4133 2198 888 2198 946 2678 946 4064 2678 4064 338 338 3352 3352 3697 32...
output:
1
result:
ok single line: '1'
Test #29:
score: 0
Accepted
time: 0ms
memory: 10304kb
input:
4900 4901 4471 4265 2181 4396 4865 4265 561 4471 4865 2987 4869 2987 4016 4869 4192 4016 4192 3026 3026 3965 3965 2851 3244 2851 3244 4583 4583 922 160 922 160 915 915 2416 4406 2416 1279 4406 4389 1279 4389 1252 4185 1252 1055 4185 2997 1055 2997 3210 3210 4862 1880 4862 1880 4217 1521 4217 1521 29...
output:
5987809
result:
ok single line: '5987809'
Test #30:
score: 0
Accepted
time: 5ms
memory: 10356kb
input:
4900 5000 1758 1814 2573 649 1034 1758 1814 3709 1034 1336 176 1336 176 369 369 2511 2511 409 4320 409 4320 3986 3986 1728 1375 1728 4449 1375 1007 4449 2519 1007 1723 2519 1199 1723 1199 3445 2058 3445 1859 2058 1859 173 173 2172 2172 4133 888 4133 2198 888 946 2198 946 2678 4064 2678 4064 338 3352...
output:
2076
result:
ok single line: '2076'
Test #31:
score: 0
Accepted
time: 4ms
memory: 9968kb
input:
4900 4904 4396 4471 4396 2987 4016 2987 4016 4471 4265 4192 4471 3828 3026 4192 3965 3026 3965 2851 2851 3244 3244 4583 922 4583 922 160 160 915 2416 915 2416 4406 4406 1279 4389 1279 1252 4389 4185 1252 4185 1055 2997 1055 3210 2997 4862 3210 4862 1880 1880 4217 1521 4217 1521 2964 4303 2964 4303 2...
output:
187272
result:
ok single line: '187272'
Test #32:
score: 0
Accepted
time: 0ms
memory: 9836kb
input:
1000 1339 451 789 544 936 344 681 87 823 381 404 734 917 427 956 731 802 78 928 21 201 521 783 685 845 526 850 37 124 94 749 222 449 122 463 97 606 26 787 251 806 644 771 39 778 90 924 259 1000 339 938 758 935 100 722 105 762 4 969 254 420 174 969 908 964 36 304 438 444 46 410 267 433 51 942 938 960...
output:
1
result:
ok single line: '1'
Test #33:
score: 0
Accepted
time: 0ms
memory: 9716kb
input:
1000 1802 298 921 626 905 238 766 63 715 257 513 417 926 288 548 414 791 63 220 674 815 327 931 863 977 539 845 25 922 540 570 746 751 504 971 73 238 22 220 166 599 386 970 27 777 478 760 177 380 238 425 425 665 74 143 78 363 5 528 169 814 112 760 449 487 25 761 296 759 34 78 180 782 34 503 453 841 ...
output:
825
result:
ok single line: '825'
Test #34:
score: 0
Accepted
time: 0ms
memory: 9684kb
input:
1000 1988 270 957 545 952 218 483 60 416 241 396 395 456 258 340 392 940 56 362 570 582 306 603 659 839 791 881 832 924 487 762 604 993 464 582 67 866 18 603 167 648 359 876 710 756 446 604 171 528 215 807 405 755 70 418 75 425 4 694 712 813 122 912 425 445 25 822 265 296 32 256 174 379 37 276 426 9...
output:
341
result:
ok single line: '341'
Test #35:
score: 0
Accepted
time: 0ms
memory: 9760kb
input:
1000 1924 278 453 582 584 221 304 65 800 240 566 396 623 267 566 393 689 59 881 603 738 315 708 711 787 885 895 25 450 522 834 642 930 489 627 74 180 16 312 167 947 373 796 776 972 462 760 174 489 217 836 405 923 76 481 81 509 4 720 779 829 119 648 439 744 24 869 270 965 33 507 177 341 37 943 445 73...
output:
1
result:
ok single line: '1'
Test #36:
score: 0
Accepted
time: 0ms
memory: 9756kb
input:
1000 1991 274 347 551 797 218 772 57 468 235 442 388 740 258 961 387 513 52 289 574 876 304 348 669 746 780 872 820 909 500 646 621 744 477 857 62 979 19 688 159 350 361 528 719 821 452 583 166 633 217 261 398 587 65 190 69 405 2 794 723 751 110 890 421 637 26 306 268 514 33 212 169 339 36 225 424 9...
output:
1
result:
ok single line: '1'
Test #37:
score: 0
Accepted
time: 4ms
memory: 9932kb
input:
1000 1928 84 196 802 973 25 622 803 916 108 189 419 440 814 950 688 903 525 530 333 688 442 953 720 991 489 688 465 688 36 860 128 785 89 419 98 291 958 980 187 546 364 733 615 780 243 642 438 518 48 706 452 952 35 130 102 641 718 875 451 592 341 443 564 632 164 719 325 392 253 618 154 261 510 688 1...
output:
1
result:
ok single line: '1'
Test #38:
score: 0
Accepted
time: 3ms
memory: 10468kb
input:
2500 5000 1351 19 1351 1742 1742 115 115 2081 2081 251 160 251 1838 160 1838 2325 2325 440 2180 440 1989 2180 1989 1143 1862 1143 1633 1862 601 1633 601 1236 1236 124 322 124 322 200 313 200 1331 313 875 1331 2029 875 347 2029 347 2014 1239 2014 1239 1932 1932 1696 2496 1696 1612 2496 613 1612 613 3...
output:
1
result:
ok single line: '1'
Test #39:
score: 0
Accepted
time: 2ms
memory: 10548kb
input:
2500 5000 1649 1880 1987 1880 1987 1647 1345 1647 1345 2333 1267 2333 1639 1267 2378 1639 2378 1601 1601 1318 1009 1318 1009 191 132 191 337 132 1103 337 286 1103 169 286 2357 169 1400 2357 2304 1400 2304 593 593 1251 1251 976 976 1901 1953 1901 1953 422 1193 422 1193 554 554 1506 2472 1506 2472 176...
output:
1
result:
ok single line: '1'
Subtask #3:
score: 11
Accepted
Dependency #1:
100%
Accepted
Test #40:
score: 11
Accepted
time: 23ms
memory: 14756kb
input:
490 60024 58 121 58 236 56 236 121 56 310 195 121 468 327 310 327 341 405 341 290 405 290 14 85 14 366 85 116 366 147 116 147 246 312 246 312 278 278 408 175 408 175 60 313 60 146 313 146 353 353 449 356 449 203 356 203 284 41 284 41 281 281 406 189 406 26 189 212 26 212 221 221 208 208 276 433 276 ...
output:
0
result:
ok single line: '0'
Test #41:
score: 0
Accepted
time: 30ms
memory: 14756kb
input:
490 60027 121 195 375 58 370 195 121 157 236 370 409 236 56 409 56 310 327 310 341 327 341 405 290 405 14 290 85 14 366 85 366 116 147 116 147 246 246 312 278 312 278 408 175 408 60 175 60 313 313 146 353 146 449 353 449 356 203 356 203 284 284 41 281 41 406 281 189 406 189 26 26 212 212 221 208 221...
output:
1
result:
ok single line: '1'
Test #42:
score: 0
Accepted
time: 32ms
memory: 15004kb
input:
500 62502 139 499 49 139 49 234 234 262 494 262 494 268 268 59 59 35 35 41 41 433 270 433 386 270 471 386 12 471 363 12 425 363 425 315 315 371 371 111 360 111 360 253 253 225 469 225 469 385 385 403 403 146 413 146 413 215 215 259 259 295 295 400 400 116 116 219 284 219 246 284 396 246 396 136 100 ...
output:
1
result:
ok single line: '1'
Subtask #4:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #43:
score: 25
Accepted
time: 173ms
memory: 34364kb
input:
4900 250000 3411 4897 3668 3411 3668 1635 4897 1635 1786 555 3874 4897 3378 1786 3378 1137 1137 3748 1519 3748 1519 2385 2631 2385 2631 72 72 4380 4380 80 80 280 280 1368 1394 1368 1394 4042 2845 4042 1363 2845 597 1363 1582 597 1582 2623 4127 2623 4127 3931 84 3931 84 2316 4011 2316 628 4011 3247 6...
output:
0
result:
ok single line: '0'
Test #44:
score: 0
Accepted
time: 156ms
memory: 34268kb
input:
4900 250000 555 4897 2786 3411 555 4592 640 4897 3668 4592 3668 1049 1049 1635 1786 1635 1786 3378 3378 1137 1137 3748 3748 1519 2385 1519 2631 2385 2631 72 72 4380 4380 80 280 80 1368 280 1394 1368 1394 4042 4042 2845 1363 2845 597 1363 1582 597 1582 2623 2623 4127 4127 3931 3931 84 84 2316 2316 40...
output:
1
result:
ok single line: '1'
Test #45:
score: 0
Accepted
time: 180ms
memory: 34468kb
input:
5000 250000 2042 4210 2577 4210 4179 2577 4179 2112 2112 70 70 1410 1410 3112 297 3112 4306 297 1621 4306 1621 1707 4702 1707 4702 3482 3482 1683 1683 2183 2183 2605 2254 2605 2254 3268 3268 2203 1425 2203 302 1425 4887 302 4887 1166 1166 2098 2098 510 3651 510 430 3651 1081 430 2543 1081 2543 3887 ...
output:
1
result:
ok single line: '1'
Subtask #5:
score: 31
Accepted
Dependency #1:
100%
Accepted
Test #46:
score: 31
Accepted
time: 17ms
memory: 16220kb
input:
100000 99999 89366 91622 12603 89366 86750 89366 8842 89366 14641 89366 41203 89366 31920 89366 89366 96734 28360 89366 48647 89366 85444 89366 75710 89366 36384 89366 6809 89366 89366 99332 32985 89366 48165 89366 57853 89366 73019 89366 32883 89366 20435 89366 63504 89366 46656 89366 57078 89366 6...
output:
1
result:
ok single line: '1'
Test #47:
score: 0
Accepted
time: 30ms
memory: 22552kb
input:
100000 99999 71282 97287 6507 99996 63733 64001 4506 60541 7606 92192 23327 63373 17503 21051 81910 97724 15366 81994 28382 68815 61930 90677 50752 70896 20255 67892 3458 79406 91827 97753 18154 40474 28047 97399 35085 83025 48103 83796 18096 73695 10801 27327 39595 42221 27005 46333 34491 51621 446...
output:
1
result:
ok single line: '1'
Test #48:
score: 0
Accepted
time: 17ms
memory: 16256kb
input:
100000 100000 52047 59665 59665 69113 59665 83945 13174 59665 59665 81134 59665 77600 27421 59665 59665 74469 59665 93945 59665 96712 32872 59665 59665 74329 59665 65436 59665 75171 59665 77952 59665 64008 59665 97796 14487 59665 59665 97693 59665 75034 19220 59665 59665 98010 4435 59665 10973 59665...
output:
3
result:
ok single line: '3'
Test #49:
score: 0
Accepted
time: 23ms
memory: 24812kb
input:
100000 100000 30703 90118 44336 63774 59821 74990 6812 21932 56433 89435 52608 79768 14774 22164 49427 53632 75357 95298 81814 95624 18048 91245 49308 51112 41129 48169 50151 93302 52995 82860 39929 79509 85110 97680 7513 27749 84734 92761 50016 90975 10100 29613 85899 93623 2240 68812 5629 22277 35...
output:
3
result:
ok single line: '3'
Test #50:
score: 0
Accepted
time: 21ms
memory: 20260kb
input:
100000 100000 30801 97154 44545 92438 60073 67655 6844 66945 56812 76338 52854 78197 14849 43566 49691 51780 75319 81189 81710 83599 18136 73974 49554 91764 41278 51954 50388 87338 53197 92982 40075 50827 84981 96946 7545 14303 84669 94070 50264 80902 10143 34482 85760 88357 2253 56982 5668 94218 35...
output:
1
result:
ok single line: '1'
Test #51:
score: 0
Accepted
time: 37ms
memory: 27236kb
input:
100000 100000 30767 54574 44372 55699 59799 72152 6805 97532 56345 84698 52578 83040 14767 17335 49396 89978 75314 81383 81872 96865 18041 35132 49275 66296 41136 94667 50109 85455 52930 55282 39926 51211 85260 96775 7503 55024 84902 93487 49980 73902 10088 84202 86028 97726 2233 71708 5623 28086 35...
output:
99999
result:
ok single line: '99999'
Test #52:
score: 0
Accepted
time: 26ms
memory: 27188kb
input:
100000 100000 30755 85428 44468 93421 59964 92461 6832 76372 56581 92396 52662 96850 14822 74330 49499 65067 75573 91512 82096 98550 18106 42397 49356 93201 41234 42805 50157 89066 53042 61629 40003 68235 85442 94576 7545 14446 85137 89150 50022 53680 10140 58315 86140 87230 2251 85077 5664 66161 35...
output:
1
result:
ok single line: '1'
Test #53:
score: 0
Accepted
time: 18ms
memory: 16116kb
input:
100000 99999 1 91622 1 12604 1 86751 1 8843 1 14642 1 41204 1 31921 1 96734 1 28361 1 48648 1 85445 1 75711 1 36385 1 6810 1 99332 1 32986 1 48166 1 57854 1 73020 1 32884 1 20436 1 63505 1 46657 1 57079 1 69281 1 9861 1 71914 1 75015 1 428 1 28193 1 8160 1 423 1 570 1 37464 1 88808 1 92439 1 99644 1...
output:
1
result:
ok single line: '1'
Test #54:
score: 0
Accepted
time: 37ms
memory: 27312kb
input:
100000 99999 91621 91622 12603 12604 86750 86751 8842 8843 14641 14642 41203 41204 31920 31921 96733 96734 28360 28361 48647 48648 85444 85445 75710 75711 36384 36385 6809 6810 99331 99332 32985 32986 48165 48166 57853 57854 73019 73020 32883 32884 20435 20436 63504 63505 46656 46657 57078 57079 692...
output:
1
result:
ok single line: '1'
Test #55:
score: 0
Accepted
time: 21ms
memory: 20636kb
input:
80000 80100 13286 16329 24065 70002 52355 57389 37245 43482 8840 25494 4906 60032 41115 55707 28608 78206 39841 44270 38935 67724 11316 18353 57632 65172 1744 36717 8868 76871 43070 46272 25385 42621 16159 73810 12402 57325 70208 79471 39418 68162 53789 74306 70143 75178 13873 64120 50415 73417 1163...
output:
39899
result:
ok single line: '39899'
Test #56:
score: 0
Accepted
time: 26ms
memory: 16972kb
input:
100000 99999 71031 77964 6512 55622 63593 80053 4533 13744 7596 33726 23296 83405 17462 62129 81827 95744 15397 50270 28269 68836 61797 78346 50650 59379 20128 83438 3494 27599 91809 91961 18083 77637 27926 85255 35024 79875 48040 65352 18029 63639 10796 34096 39479 60599 26950 61478 34422 36660 445...
output:
1
result:
ok single line: '1'
Test #57:
score: 0
Accepted
time: 29ms
memory: 21712kb
input:
100000 100100 3219 47727 82510 87616 34527 95559 51772 81628 25606 43364 16608 98054 12305 40411 13702 60209 18874 56075 64069 68780 12628 53125 22764 58332 3946 29805 9985 30781 19125 34047 53814 72897 27669 36609 30254 96597 88307 90955 94803 99930 33463 42386 22761 68939 22937 40625 73957 89169 5...
output:
1
result:
ok single line: '1'
Test #58:
score: 0
Accepted
time: 33ms
memory: 21836kb
input:
100000 100100 3192 69847 82628 86144 34584 82913 51799 69422 25591 98822 16536 47671 12259 98927 13664 92773 18789 62163 64032 85891 12600 94482 22740 83198 3909 25631 9941 95009 19036 98184 53856 98302 27677 73503 30275 42880 88467 95690 95277 97614 33518 61897 22738 32636 22911 95932 73953 76551 5...
output:
19676
result:
ok single line: '19676'
Test #59:
score: 0
Accepted
time: 27ms
memory: 23492kb
input:
100000 100100 3245 35185 82655 91380 34544 44074 51864 84518 25635 42996 16561 26376 12285 66381 13685 59022 18827 82358 64133 74224 12624 25164 22733 88104 3946 56773 9942 25895 19078 38891 53993 74263 27663 86511 30214 67752 88507 94773 94988 98737 33452 54813 22730 97029 22897 42466 74001 91609 5...
output:
55249
result:
ok single line: '55249'
Test #60:
score: 0
Accepted
time: 28ms
memory: 19492kb
input:
100000 100100 3187 82234 82779 87397 34522 42196 51678 95389 25561 70821 16536 56652 12253 17066 13689 79288 18801 94797 63897 92516 12601 65144 22715 28149 3897 68881 9916 21294 19046 75231 53772 86987 27626 62438 30210 33140 88515 95534 94822 98585 33500 47514 22711 88166 22891 50469 73923 89009 5...
output:
1
result:
ok single line: '1'
Test #61:
score: 0
Accepted
time: 33ms
memory: 16888kb
input:
100000 100086 42854 79349 35449 90716 24753 79104 48422 53549 3207 51247 50043 90570 69369 76898 45547 69511 27794 56980 27984 64590 60656 70939 20932 39458 20007 24572 16475 16773 35104 98562 8691 32704 8468 59411 38934 98796 31804 40062 10467 35694 2029 59590 93891 97624 21166 54812 94419 94563 38...
output:
4
result:
ok single line: '4'
Test #62:
score: 0
Accepted
time: 29ms
memory: 19752kb
input:
100000 100100 3175 35751 82677 95396 34483 50051 51619 67979 25584 44543 16574 46319 12266 33146 13697 64508 18843 60636 63880 64592 12609 19737 22767 59740 3878 65570 9926 65822 19086 87768 53679 57893 27681 51713 30190 99403 88203 96811 94815 99355 33427 68879 22763 67711 22946 32672 73817 78915 5...
output:
1
result:
ok single line: '1'
Test #63:
score: 0
Accepted
time: 16ms
memory: 16344kb
input:
100000 99999 1 91622 1 12604 1 86751 1 8843 1 14642 1 41204 1 31921 1 96734 1 28361 1 48648 1 85445 1 75711 1 36385 1 6810 1 99332 1 32986 1 48166 1 57854 1 73020 1 32884 1 20436 1 63505 1 46657 1 57079 1 69281 1 9861 1 71914 1 75015 1 428 1 28193 1 8160 1 423 1 570 1 37464 1 88808 1 92439 1 99644 1...
output:
1
result:
ok single line: '1'
Test #64:
score: 0
Accepted
time: 33ms
memory: 16820kb
input:
100000 99999 70980 79865 6504 49942 63509 81202 4501 7353 7600 81618 23296 48498 17387 34066 81867 84806 15316 38945 28375 85802 61821 83191 50690 57429 20159 48596 3449 89694 91771 99815 18056 63239 28043 45976 35206 39102 48132 75644 17989 72324 10790 94281 39717 84138 26986 51782 34613 67866 4471...
output:
1
result:
ok single line: '1'
Test #65:
score: 0
Accepted
time: 5ms
memory: 10888kb
input:
10000 10004 6193 5537 6193 6237 6237 2323 2323 5537 3905 6717 8752 5537 6717 4239 6529 4239 6529 5474 5474 1310 4413 1310 9583 4413 8853 9583 8853 3201 5733 3201 1079 5733 3744 1079 1650 3744 1650 5327 5327 8284 8284 2727 2727 6044 8310 6044 58 8310 2129 58 6982 2129 5675 6982 5369 5675 5369 8051 28...
output:
3125000
result:
ok single line: '3125000'
Test #66:
score: 0
Accepted
time: 30ms
memory: 23236kb
input:
100000 100004 21738 44834 44834 96576 28451 96576 21738 28451 56449 3444 21738 70717 13029 3444 13029 66039 8955 66039 8955 51445 30706 51445 27229 30706 37159 27229 66052 37159 16691 66052 16691 70389 70389 29935 44984 29935 44984 3648 75082 3648 73600 75082 73600 76621 76621 28345 5298 28345 37940...
output:
312500000
result:
ok single line: '312500000'
Test #67:
score: 0
Accepted
time: 21ms
memory: 25348kb
input:
100000 100200 69871 68949 68949 59779 10238 59779 10238 69871 30874 18991 69871 4542 36490 18991 36490 68599 76141 68599 76141 42745 86716 42745 86716 92294 92294 49277 20505 49277 20505 53300 53300 47675 95673 47675 95673 87582 19445 87582 19445 24950 25239 24950 10225 25239 10225 51730 90007 51730...
output:
20706
result:
ok single line: '20706'
Test #68:
score: 0
Accepted
time: 76ms
memory: 52320kb
input:
249700 249900 112573 62051 220612 62051 220612 149429 149429 112573 6050 151192 188206 112573 231593 6050 46268 231593 46268 210321 210321 27335 101279 27335 80501 101279 80501 112364 112364 42269 42269 59274 168806 59274 168806 39620 39620 94374 94374 6587 6587 87922 115009 87922 115009 248684 2205...
output:
57860
result:
ok single line: '57860'
Test #69:
score: 0
Accepted
time: 94ms
memory: 45452kb
input:
249900 249904 132780 79828 185043 79828 185043 152827 152827 132780 27925 78603 132780 96955 171181 78603 45175 171181 45175 146496 124418 146496 124418 70666 51665 70666 112123 51665 74248 112123 81853 74248 110663 81853 123019 110663 37848 123019 37848 201461 201461 180599 25282 180599 25282 18672...
output:
1951375392
result:
ok single line: '1951375392'
Test #70:
score: 0
Accepted
time: 6ms
memory: 11200kb
input:
10000 10001 6646 3640 8141 9311 702 3640 6646 1418 702 9120 9120 1733 5501 1733 8770 5501 8770 8462 8462 5205 7487 5205 7487 4479 7678 4479 5762 7678 4786 5762 6096 4786 6096 1009 2483 1009 5647 2483 6703 5647 6703 1814 1814 360 4207 360 275 4207 5629 275 1153 5629 2150 1153 2150 7009 7009 8809 4670...
output:
24970009
result:
ok single line: '24970009'
Test #71:
score: 0
Accepted
time: 24ms
memory: 21808kb
input:
100000 100001 84975 12499 93622 84271 84975 94070 23882 12499 94070 64812 16797 64812 8509 16797 8509 5404 5404 97839 97839 69732 69732 94155 34732 94155 38791 34732 38791 45255 19913 45255 63444 19913 17098 63444 17098 25189 25189 8739 8739 22666 3308 22666 3308 92077 92077 63796 24090 63796 54927 ...
output:
2499700009
result:
ok single line: '2499700009'
Test #72:
score: 0
Accepted
time: 36ms
memory: 27144kb
input:
100000 100200 69871 30874 42621 68949 93685 30874 23219 69871 59779 93685 59779 19306 19306 10238 18991 10238 18991 36490 36490 68599 76141 68599 76141 42745 86716 42745 86716 92294 49277 92294 20505 49277 20505 53300 47675 53300 47675 95673 95673 87582 87582 19445 19445 24950 25239 24950 25239 1022...
output:
348153
result:
ok single line: '348153'
Test #73:
score: 0
Accepted
time: 90ms
memory: 54124kb
input:
249700 249900 112573 151192 62051 149349 151192 187898 20981 112573 220612 187898 83150 220612 83150 149429 149429 6050 6050 231593 46268 231593 46268 210321 210321 27335 27335 101279 101279 80501 112364 80501 112364 42269 59274 42269 59274 168806 39620 168806 94374 39620 94374 6587 6587 87922 87922...
output:
1229666
result:
ok single line: '1229666'
Test #74:
score: 0
Accepted
time: 76ms
memory: 48852kb
input:
249900 249901 27925 132780 79828 76726 27925 147995 107119 132780 147995 185043 244039 185043 152827 244039 78603 152827 78603 171181 45175 171181 45175 146496 124418 146496 70666 124418 51665 70666 112123 51665 74248 112123 81853 74248 110663 81853 110663 123019 123019 37848 201461 37848 201461 180...
output:
15611752809
result:
ok single line: '15611752809'
Test #75:
score: 0
Accepted
time: 26ms
memory: 19984kb
input:
100000 100004 12499 93622 64812 93622 64812 8509 8509 12499 84975 5404 12499 81280 97839 5404 97839 69732 69732 94155 94155 34732 34732 38791 45255 38791 19913 45255 19913 63444 17098 63444 25189 17098 8739 25189 8739 22666 22666 3308 3308 92077 63796 92077 63796 24090 24090 54927 82926 54927 31640 ...
output:
78125000
result:
ok single line: '78125000'
Test #76:
score: 0
Accepted
time: 79ms
memory: 36432kb
input:
249900 249904 159271 109649 109649 111599 111599 35804 35804 159271 190871 238627 159271 198121 181943 238627 181943 1652 91355 1652 91355 62710 62710 125361 36731 125361 36731 146493 146493 32864 32864 89456 89456 159459 159459 97007 97007 55549 55549 49249 49249 112119 112119 41791 99036 41791 783...
output:
487843848
result:
ok single line: '487843848'
Subtask #6:
score: 50
Accepted
Test #77:
score: 50
Accepted
time: 39ms
memory: 24508kb
input:
100000 108983 21404 28497 13689 70925 71958 74068 2781 97683 46835 69049 17997 38493 21756 76722 6630 95872 639 58783 28329 31299 24091 35440 40913 82273 38109 62691 4771 19453 62755 70375 74893 92009 9025 17849 1191 99151 51850 69612 40615 60737 69125 86355 70084 86364 64153 97666 53694 77948 27564...
output:
38180
result:
ok single line: '38180'
Test #78:
score: 0
Accepted
time: 48ms
memory: 23448kb
input:
100000 109000 27707 68530 592 32866 30670 38748 27262 52892 51114 94895 34640 93889 12424 22032 41275 98947 7912 29103 11149 40882 14235 47607 16048 49440 2472 25164 10378 81306 37728 65110 42214 62280 18595 94650 16802 98910 37660 82493 41491 89104 13152 84110 4558 90674 62853 70767 48530 50013 128...
output:
24969
result:
ok single line: '24969'
Test #79:
score: 0
Accepted
time: 119ms
memory: 34168kb
input:
100000 190844 13585 67402 32308 38320 31641 32411 12059 42183 40368 46576 49145 83830 23435 67024 48554 65783 360 41809 49690 61779 44873 85071 29405 54993 36235 90782 2419 68841 14362 83379 66794 96037 48566 60148 5026 91369 22289 94901 54891 55832 76527 86739 674 17495 26947 52337 17013 59294 3129...
output:
1
result:
ok single line: '1'
Test #80:
score: 0
Accepted
time: 107ms
memory: 35024kb
input:
100000 194584 87732 90808 42047 76222 13420 43242 9782 50201 6923 34878 2663 21591 55883 66067 54331 88112 88915 94705 57706 65336 59704 60396 34732 60683 21225 51922 55132 74153 3067 11247 5344 88565 39971 87907 63857 72342 37163 98822 20807 94565 51333 59071 26480 37289 4289 60980 18177 55294 3432...
output:
43360
result:
ok single line: '43360'
Test #81:
score: 0
Accepted
time: 112ms
memory: 33264kb
input:
100000 199939 70416 73740 75586 75638 71450 85096 63327 65018 48442 90771 8530 15589 37382 38390 37283 63532 16780 20903 24930 56513 65124 85977 44246 99362 45945 82907 4014 15561 31426 47134 31466 52535 282 40706 6200 15065 21886 28276 905 39852 46000 54889 73239 76576 19036 55173 17378 53119 13358...
output:
17389
result:
ok single line: '17389'
Test #82:
score: 0
Accepted
time: 146ms
memory: 38660kb
input:
100000 199984 7447 46857 9557 11457 7059 72433 28315 41209 10160 13204 62259 79002 7077 79377 88037 94214 1186 96505 31099 88035 31748 66238 11862 38368 71669 92960 72455 90720 7839 51902 1163 77623 58255 83799 52348 98051 39071 52755 17802 44490 32995 36579 3751 91493 187 77278 49537 75024 17719 80...
output:
1
result:
ok single line: '1'
Test #83:
score: 0
Accepted
time: 127ms
memory: 31380kb
input:
100000 181221 35628 99578 16271 95829 40 50284 78559 91482 27156 66558 12769 77608 72263 86992 72285 96603 37106 49734 38810 92181 53380 79666 22183 33285 44440 58562 53515 78880 54362 68580 9625 44440 36721 81728 29548 42240 42359 96705 23802 97034 4824 63574 38313 83808 10981 80801 54362 82136 307...
output:
0
result:
ok single line: '0'
Test #84:
score: 0
Accepted
time: 133ms
memory: 39020kb
input:
100000 199998 39600 42845 49274 57272 2834 91710 79755 80684 3558 53829 34319 65614 77081 91491 55299 91569 57795 59532 60832 75080 71661 86774 29469 29706 4639 71454 28919 48586 85159 93732 61677 94036 21529 70066 10551 97127 49909 86898 13907 97182 62244 99362 27728 89866 15911 69916 16252 71910 1...
output:
1
result:
ok single line: '1'
Test #85:
score: 0
Accepted
time: 39ms
memory: 22912kb
input:
100000 121568 22260 85459 29201 53730 474 37110 24532 65787 43760 48458 93174 98132 14910 72987 22191 49743 25448 98205 25101 62908 1666 38234 34791 97563 70105 84319 14123 88571 26885 27688 28637 88796 36019 60891 46484 52698 83717 91334 267 18279 24162 69211 11203 87216 2606 26133 6888 76567 1952 ...
output:
18
result:
ok single line: '18'
Test #86:
score: 0
Accepted
time: 91ms
memory: 36088kb
input:
100000 199949 60578 76731 74607 78617 18117 24307 47943 82642 47348 69863 5542 46076 31872 54566 48983 78464 43345 47633 29569 63294 32012 96520 22995 55339 35519 99963 79577 95442 6898 57819 12497 85659 32310 61160 52125 80084 47746 97712 17999 91141 17526 46999 11624 74672 84407 99933 164 53742 49...
output:
57034
result:
ok single line: '57034'
Test #87:
score: 0
Accepted
time: 154ms
memory: 39256kb
input:
100000 200250 78758 86284 30024 43760 2646 73259 71370 96998 27840 52149 12430 18266 29089 77209 32901 40834 24514 32003 42334 84288 16518 95701 96080 97449 5771 78386 20554 72594 25863 92024 8212 21491 31245 82796 2738 4249 31771 70957 5355 33958 19064 32627 13144 25358 45464 56436 5470 44208 74036...
output:
2
result:
ok single line: '2'
Test #88:
score: 0
Accepted
time: 74ms
memory: 32396kb
input:
100000 165921 1314 24368 14863 22958 3710 34917 52168 53729 95968 99700 62454 65065 24995 29987 39213 87819 88822 91217 77302 84671 23649 65261 64686 80889 34930 83075 13703 99743 10432 77473 37655 98488 1977 34917 67125 98339 17423 85726 33473 55054 38293 39656 27558 37084 34442 45799 9186 56044 13...
output:
33845
result:
ok single line: '33845'
Test #89:
score: 0
Accepted
time: 115ms
memory: 37220kb
input:
100000 232906 50906 56521 68568 77835 6911 35687 76633 93558 61931 79821 26845 44191 49195 54111 15123 88339 5390 32629 18812 21113 73522 99560 10800 88429 30151 97522 21059 92541 23 94739 5840 66669 22070 97159 59273 68563 16516 64067 19219 66675 54839 60838 48936 89769 85887 94665 52613 86854 3217...
output:
1
result:
ok single line: '1'
Test #90:
score: 0
Accepted
time: 31ms
memory: 21164kb
input:
100000 104176 15843 69599 16816 88180 35504 63115 1736 49154 84922 91033 45336 57072 46033 70225 6560 80104 39194 99327 1323 81518 19003 21864 11105 83683 29295 75822 20853 36582 19432 25652 46660 48401 60429 83647 89064 91255 26673 44271 65939 76831 18450 49031 3489 75716 3393 71935 32820 92602 212...
output:
35184
result:
ok single line: '35184'
Test #91:
score: 0
Accepted
time: 209ms
memory: 49344kb
input:
100000 250000 82100 73901 73901 81778 81778 66062 66062 82100 17240 65761 82100 44942 95027 17240 78407 95027 16629 78407 16629 94367 94367 54004 78562 54004 78562 63638 63638 75398 62119 75398 33265 62119 33265 26587 75813 26587 34756 75813 34756 10352 10352 40589 40589 18861 18861 69930 23584 6993...
output:
0
result:
ok single line: '0'
Test #92:
score: 0
Accepted
time: 203ms
memory: 49096kb
input:
100000 250000 65761 82100 86110 73901 43110 65761 82100 87158 81778 43110 57498 81778 66062 57498 66062 17240 17240 95027 78407 95027 78407 16629 16629 94367 54004 94367 78562 54004 78562 63638 75398 63638 62119 75398 62119 33265 33265 26587 26587 75813 75813 34756 10352 34756 10352 40589 18861 4058...
output:
1
result:
ok single line: '1'
Test #93:
score: 0
Accepted
time: 188ms
memory: 51220kb
input:
125000 250000 108222 39400 39400 12542 771 12542 64928 771 64928 51355 54503 51355 84228 54503 84228 3568 107388 3568 107388 6455 6455 108837 108837 83974 78400 83974 78400 43929 11731 43929 97006 11731 97006 14891 14891 95875 95875 35925 42052 35925 42052 2931 2931 6961 6961 69639 69639 15677 15677...
output:
1
result:
ok single line: '1'
Test #94:
score: 0
Accepted
time: 174ms
memory: 56576kb
input:
200000 250000 84310 392 113863 392 82924 113863 82924 130124 130124 148414 92218 148414 92218 129050 189802 129050 175430 189802 175430 58315 84166 58315 84166 55611 55611 119455 119455 84496 84496 58252 58252 8378 177677 8378 177677 166610 166610 79823 79823 197232 124275 197232 124275 85036 85036 ...
output:
1
result:
ok single line: '1'
Test #95:
score: 0
Accepted
time: 215ms
memory: 41680kb
input:
50000 250000 41990 44341 41990 6279 49629 6279 49629 16461 45931 16461 10675 45931 15594 10675 15594 44976 19395 44976 19395 3281 44915 3281 44915 4373 12871 4373 12871 36398 14749 36398 14749 28126 28126 27264 27264 4198 37926 4198 18152 37926 18152 49848 40600 49848 16597 40600 46945 16597 49374 4...
output:
1
result:
ok single line: '1'