QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#587227 | #9377. Points Selection | fallleaves01 | AC ✓ | 776ms | 27956kb | C++20 | 2.4kb | 2024-09-24 18:35:04 | 2024-09-24 18:35:04 |
Judging History
answer
#include <bits/stdc++.h>
//#define DEBUG
using namespace std;
using u64 = uint64_t;
using bs = bitset<500000>;
bs mask;
mt19937 rd(random_device{}());
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n = 1000;
#ifndef DEBUG
cin >> n;
#endif
for (int i = 0; i <= n; i++) {
mask[i] = 1;
}
vector<vector<pair<int, int>>> p(n + 1);
for (int i = 1; i <= n; i++) {
int x, y, c;
#ifdef DEBUG
x = rd() % n + 1, y = rd() % n + 1, c = rd() % n + 1;
#else
cin >> x >> y >> c;
#endif
p[x].push_back({y, c});
}
struct Val {
bs s;
int x, n;
u64 sum;
void add(int c) {
bs ns = s | (s << c) | (s >> (n - c)), tmp = ns ^ s;
for (int i = tmp._Find_first(); i < n; i = tmp._Find_next(i)) {
sum += i;
}
s = ns;
}
bool full() const { return sum == n * (n - 1ull) / 2; }
};
vector<Val> f = {Val{1, 0, n, 0}};
auto calc = [&](int l, int r) { return (l + r) * (r - l + 1ll) / 2; };
auto query = [&]() -> u64 {
u64 res = 0;
for (int i = 0; i + 1 < (int)f.size(); i++) {
res += f[i].sum * calc(f[i].x, f[i + 1].x - 1);
}
res += f.back().sum * calc(f.back().x, n);
return res;
};
u64 ans = 0;
int tag = 0, mxc = 0;
for (int i = 1; i <= n; i++) {
sort(p[i].begin(), p[i].end());
for (auto [y, c] : p[i]) {
if (!f.back().full() || y < f.back().x) {
for (int j = 0; j < (int)f.size(); j++) {
if (j + 1 == (int)f.size() || f[j + 1].x > y) {
f.insert(f.begin() + j + 1, f[j]);
f[j + 1].x = y;
for (int k = j + 1; k < (int)f.size(); k++) {
f[k].add(c);
++tag;
}
while ((int)f.size() >= 2 && f.end()[-2].full()) {
f.pop_back();
}
break;
}
}
}
}
mxc = max(mxc, (int)f.size());
ans += query() * i;
}
cerr << tag << ' ' << mxc << '\n';
cout << ans << '\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3988kb
input:
3 1 2 2 2 3 1 3 1 3
output:
75
result:
ok single line: '75'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
5 1 1 4 5 1 4 2 3 3 1 4 1 2 5 2
output:
1935
result:
ok single line: '1935'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
2 2 2 1 2 2 2
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4040kb
input:
10 1 8 8 2 1 1 8 7 7 7 3 4 7 3 9 7 7 7 10 7 6 6 3 2 4 8 6 4 1 7
output:
111023
result:
ok single line: '111023'
Test #5:
score: 0
Accepted
time: 4ms
memory: 4432kb
input:
50 36 15 31 32 26 25 50 22 26 36 41 49 39 35 49 3 2 18 33 18 23 45 1 15 36 47 4 3 23 34 29 16 49 25 27 48 40 15 33 50 50 3 49 14 40 6 31 36 4 1 22 1 35 36 26 49 21 48 29 32 46 36 36 41 23 41 48 32 10 30 31 8 39 20 15 16 39 39 1 27 39 2 32 27 20 31 5 20 21 7 37 11 39 35 30 24 36 10 10 39 29 1 9 39 2 ...
output:
1789215309
result:
ok single line: '1789215309'
Test #6:
score: 0
Accepted
time: 4ms
memory: 4420kb
input:
100 32 14 15 96 28 65 48 93 33 20 57 28 90 20 32 53 57 42 94 58 18 29 27 21 94 22 37 60 67 45 20 23 83 93 35 23 6 42 3 46 68 46 17 25 34 5 50 16 23 91 49 100 69 76 81 68 58 41 88 32 37 29 64 25 95 13 74 59 6 35 31 58 13 80 16 59 10 80 16 18 85 40 51 70 8 28 44 87 8 76 28 86 53 73 2 100 52 100 14 83 ...
output:
122168185226
result:
ok single line: '122168185226'
Test #7:
score: 0
Accepted
time: 6ms
memory: 4496kb
input:
200 113 168 160 83 105 119 131 49 125 10 101 68 107 143 69 75 11 72 171 198 163 186 7 134 155 143 154 178 37 157 56 14 154 23 39 24 21 84 178 38 87 142 5 126 88 123 90 28 167 4 7 100 197 58 90 158 97 44 92 83 115 69 85 114 161 144 4 150 129 146 113 111 143 59 131 12 93 32 172 165 93 179 79 200 159 1...
output:
7982708300950
result:
ok single line: '7982708300950'
Test #8:
score: 0
Accepted
time: 14ms
memory: 4448kb
input:
500 238 21 289 225 123 284 177 119 289 381 336 391 450 104 77 38 478 132 17 144 397 65 244 466 434 402 287 353 140 198 253 391 77 16 248 154 453 296 103 185 334 433 348 404 459 478 414 363 218 454 495 180 466 325 57 119 404 378 17 36 148 374 424 61 141 434 406 239 100 3 76 461 242 481 459 467 50 200...
output:
1952381973315934
result:
ok single line: '1952381973315934'
Test #9:
score: 0
Accepted
time: 21ms
memory: 4492kb
input:
1000 325 197 894 183 902 232 495 481 41 704 152 266 546 458 790 366 30 258 332 546 747 683 523 816 647 152 771 793 785 967 864 915 62 536 972 667 290 183 678 374 533 164 508 943 932 823 226 627 767 596 644 613 563 620 813 340 53 752 591 164 326 342 990 25 97 157 732 373 197 539 693 224 642 835 826 6...
output:
124972421832399589
result:
ok single line: '124972421832399589'
Test #10:
score: 0
Accepted
time: 29ms
memory: 5612kb
input:
2000 1493 1415 271 953 895 921 909 322 585 1803 1116 77 1756 964 892 659 1374 1407 1597 1341 933 906 1547 1828 1556 133 1573 1287 104 1421 233 322 75 1064 1519 464 657 730 817 1570 126 1075 1583 1434 426 1978 1554 1785 906 1126 1785 275 613 1585 1167 1572 1475 505 581 764 281 1539 1977 1854 1766 153...
output:
7999820596225906065
result:
ok single line: '7999820596225906065'
Test #11:
score: 0
Accepted
time: 35ms
memory: 5664kb
input:
4000 3318 2747 2643 1279 3072 1706 3530 2197 1863 2305 2533 3891 1471 1463 2502 1757 3869 1911 2126 3828 2713 3657 106 1260 991 3774 585 1570 853 2522 970 32 2614 2631 420 1851 1584 1630 2584 1752 2015 3600 2133 1904 821 2992 2596 998 288 3164 3555 1791 1800 1323 3284 1714 3808 1419 880 42 2704 333 ...
output:
13997528416047757885
result:
ok single line: '13997528416047757885'
Test #12:
score: 0
Accepted
time: 48ms
memory: 6036kb
input:
10000 3019 6058 8581 4553 4140 2151 9170 9883 5920 6945 1527 318 6709 5007 5345 7507 7659 7960 4849 3939 7188 9064 7426 3336 9265 9262 4765 2298 8985 8162 9622 7280 9285 8691 3897 3652 682 6185 4135 8233 7107 2484 7526 9867 8426 2777 574 314 7617 5363 4928 8482 9748 9583 5339 1701 9103 1300 4875 951...
output:
14516232941283257612
result:
ok single line: '14516232941283257612'
Test #13:
score: 0
Accepted
time: 77ms
memory: 6876kb
input:
30000 4630 17717 13881 9825 2299 1192 2753 10951 26935 25619 27515 27102 6346 3545 183 21397 29103 7269 19868 15303 14685 5289 5140 19399 13697 13176 13207 2839 11630 17903 736 16848 1163 26137 23356 15956 9780 9510 24418 29846 27181 4521 6957 12034 3315 3902 9106 26098 24891 20363 13859 6055 18645 ...
output:
18214800153086918568
result:
ok single line: '18214800153086918568'
Test #14:
score: 0
Accepted
time: 112ms
memory: 7832kb
input:
50000 23137 10864 17692 7801 13161 40234 13632 36612 45246 1590 17696 29693 21391 13571 12317 45687 7843 9281 17991 20858 39078 11113 35558 32357 2322 15602 8946 29188 11570 24939 14953 26417 21553 28991 2816 30965 16173 42836 48893 41459 21447 43854 10580 26906 38205 45028 37638 31882 5270 32659 20...
output:
4189860286292203646
result:
ok single line: '4189860286292203646'
Test #15:
score: 0
Accepted
time: 182ms
memory: 10052kb
input:
100000 54586 97259 41764 74257 75415 18013 75008 38133 49107 16804 4815 21009 55609 58668 63480 71333 27967 25834 70841 28878 87172 21498 96676 52932 99091 5815 37196 78764 87715 7677 65966 27528 76077 18066 82836 61689 99404 1173 33984 31931 32432 63348 60344 11566 95744 37984 26588 46798 6768 3220...
output:
4498101256365314741
result:
ok single line: '4498101256365314741'
Test #16:
score: 0
Accepted
time: 388ms
memory: 16608kb
input:
250000 68158 20607 121543 199932 65487 231570 142529 79651 239942 204791 217581 45796 32970 173655 74177 240346 55975 91760 160207 208839 94310 40261 48193 11464 151019 144925 86874 78554 163019 44155 93099 36763 30043 135068 119420 88660 129099 125893 115718 110298 19452 241721 154560 137955 20795 ...
output:
17507893107724593257
result:
ok single line: '17507893107724593257'
Test #17:
score: 0
Accepted
time: 465ms
memory: 20472kb
input:
333333 13009 75117 51391 242161 317842 66615 316257 185319 275454 129909 222387 322813 157669 78900 85170 74864 38036 70687 64590 73920 221068 163983 283834 290289 163693 264165 150267 214204 298092 295739 298402 145018 182772 129396 194740 116612 36710 283635 260433 226288 68543 183730 197887 24595...
output:
11553651545492121229
result:
ok single line: '11553651545492121229'
Test #18:
score: 0
Accepted
time: 679ms
memory: 27812kb
input:
500000 183146 2649 54639 374622 429384 400586 224634 123745 147824 180284 279559 426023 251566 206488 362581 905 258017 93303 101176 245926 483252 464909 467390 326053 360005 228299 459529 220880 261783 412134 363480 104703 27829 495161 117872 438171 238153 120392 199319 113734 18547 490058 388190 2...
output:
13566189362432660473
result:
ok single line: '13566189362432660473'
Test #19:
score: 0
Accepted
time: 692ms
memory: 27792kb
input:
500000 187892 51493 138063 44887 278638 30064 158789 307733 176703 240027 315807 230205 413377 32922 129967 281167 262635 41220 164925 42871 413974 30780 74899 441127 421522 314316 306090 20751 443392 369699 481580 390781 47056 89761 419981 414308 325391 350467 290945 199145 234648 23273 46378 30158...
output:
2645341757068780104
result:
ok single line: '2645341757068780104'
Test #20:
score: 0
Accepted
time: 718ms
memory: 27864kb
input:
500000 468446 100338 254191 23663 160596 192245 125648 491721 448686 75579 76246 34388 416404 102459 430057 252917 10358 213330 228673 339816 311992 405163 182409 397416 15743 157228 119947 320621 433512 18752 291167 401052 33578 427465 478986 357740 412628 304734 125675 93067 142237 280680 480375 3...
output:
7611958253216647537
result:
ok single line: '7611958253216647537'
Test #21:
score: 0
Accepted
time: 641ms
memory: 27948kb
input:
500000 473191 116478 337615 469736 252953 45915 59804 208413 412158 135323 369390 338570 354023 428892 262852 476 258080 161247 16614 412568 210010 279547 65726 45194 109965 467436 433804 120491 147824 443613 133458 187130 276996 54770 281094 333877 499866 2105 460405 178478 391041 346598 138564 403...
output:
3123035105205489424
result:
ok single line: '3123035105205489424'
Test #22:
score: 0
Accepted
time: 749ms
memory: 27952kb
input:
500000 286449 165322 421039 172705 102207 142689 26663 359697 216845 162362 129830 142752 81242 255325 338750 472226 229995 141868 113066 176809 140732 121226 173235 192972 171482 53452 247661 420362 362137 368474 251557 197401 328926 392474 83203 277309 119807 264884 295134 296592 331334 104005 329...
output:
6321536538201583028
result:
ok single line: '6321536538201583028'
Test #23:
score: 0
Accepted
time: 698ms
memory: 27796kb
input:
500000 291195 246871 4463 151482 451460 304870 493523 76389 488828 222106 390269 446934 18861 357566 138840 252488 10421 89785 176815 249562 71454 495609 280745 116558 265703 363661 94222 187528 319553 17527 61144 483479 348152 487074 142208 253445 174341 462255 129864 190515 271627 394116 263453 47...
output:
11302356233919048927
result:
ok single line: '11302356233919048927'
Test #24:
score: 0
Accepted
time: 771ms
memory: 27956kb
input:
500000 71748 38819 120591 97555 76522 434348 427678 260377 485003 281850 150709 251117 246080 151296 471634 224238 15039 37702 464755 13803 2176 61480 388254 264335 327220 239277 408079 487398 33865 475092 403435 461045 91570 357482 444317 164174 261579 192330 497298 275925 20432 394626 454346 39267...
output:
15422409318020907602
result:
ok single line: '15422409318020907602'
Test #25:
score: 0
Accepted
time: 755ms
memory: 27872kb
input:
500000 385006 87663 204015 300523 425775 96530 137642 411661 256987 84697 411148 55299 183699 253537 271725 4501 262762 485619 28504 278043 400194 435864 271571 444817 421441 49485 478832 287268 56690 367249 213022 279828 78093 452082 279129 140310 381520 422405 332028 394040 428020 184737 388342 29...
output:
7869472848036550063
result:
ok single line: '7869472848036550063'
Test #26:
score: 0
Accepted
time: 776ms
memory: 27944kb
input:
500000 422456 103804 287439 279300 18133 450199 104501 128353 285866 144441 204292 359481 378214 47266 71815 476251 234676 157728 124956 350796 298213 310247 379080 59891 48366 135501 325393 362947 238298 16302 331121 290098 97319 322490 81238 83742 468758 119775 166757 255258 144121 442144 46531 33...
output:
5800979043946239494
result:
ok single line: '5800979043946239494'
Test #27:
score: 0
Accepted
time: 697ms
memory: 27808kb
input:
500000 203009 152648 403567 258077 367386 112381 38657 279637 25145 171481 240540 163664 348537 149507 371905 256513 15103 138349 188705 115037 228935 184630 486590 483476 109883 445710 139250 97409 228418 473866 173412 267665 340737 417091 107539 59879 55995 382554 1487 373373 117118 8062 204720 39...
output:
17531527689244056115
result:
ok single line: '17531527689244056115'
Extra Test:
score: 0
Extra Test Passed