QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#524749 | #6337. Mizuyokan 2 | Qwerty1232# | 0 | 192ms | 4932kb | C++23 | 1.7kb | 2024-08-20 04:20:40 | 2024-08-20 04:20:40 |
Judging History
answer
#include <bits/stdc++.h>
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> input(n);
for (auto& i : input) {
std::cin >> i;
}
int q;
std::cin >> q;
std::vector<std::array<int, 4>> quer(q);
for (auto& [x, y, l, r] : quer) {
std::cin >> x >> y >> l >> r;
x--;
}
std::vector<int> ans(q);
for (int i = 0; i < q; i++) {
auto& [x, y, l, r] = quer[i];
input[x] = y;
std::vector<int> vec(input.begin() + l, input.begin() + r);
int n = vec.size();
std::vector<int> dp(n, -1e3);
dp[0] = 1;
constexpr int K = 1e9;
for (int i = 0; i + 1 < std::min(n, K); i++) {
if (std::accumulate(vec.begin(), vec.begin() + i, 0ll) > vec[i]) {
dp[i] = 2;
}
}
for (int i = 0; i < n; i++) {
int64_t sum = 0;
int val = dp[i];
for (int j = i - 1; j > std::max(0, i - K); j--) {
sum += vec[j];
if (vec[i] < sum && vec[j - 1] < sum) {
val = std::max(val, dp[j - 1] + 2);
}
}
dp[i] = val;
}
int& res = ans[i];
res = std::max(1, dp[n - 1]);
for (int i = std::max(0, n - K); i < n; i++) {
if (std::accumulate(vec.begin() + i + 1, vec.begin() + n, 0ll) > vec[i]) {
res = std::max(res, dp[i] + 1);
}
}
}
for (int i = 0; i < q; i++) {
std::cout << ans[i] << "\n";
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 1ms
memory: 3532kb
input:
170 581553716 290776853 145388421 581553716 168947671 936760822 849346471 126291564 133104657 125887494 136786623 123143788 137803872 129733949 849346471 880499329 202732710 611312524 152828126 305656257 611312524 121295297 6875889 74507235 419967909 333601507 281557968 740824934 370412466 185206229...
output:
59 56 61 61 56 37 42 46
result:
ok 8 numbers
Test #2:
score: 6
Accepted
time: 1ms
memory: 3612kb
input:
200 517847507 258923750 129461870 517847507 106915073 712580593 512811829 12657894 12715954 12534704 12759073 12554236 12685369 12563357 12817887 12534566 12752501 12518874 12746471 12524663 12730053 12586182 12803851 12628464 12778716 12645600 12701929 12550298 12754947 12548765 12765210 12592487 1...
output:
118 162 114 113 143 105 109 165 139 152
result:
ok 10 numbers
Test #3:
score: 6
Accepted
time: 0ms
memory: 3524kb
input:
156 689580506 344790254 172395128 689580506 344790254 689580506 344790252 172395125 86197561 86197567 86197565 86197566 43098784 86197566 86197565 86197567 86197561 172395125 344790252 689580506 344790254 689580506 172395128 344790254 689580506 3985467 453082635 861305238 430652620 215326311 8613052...
output:
19 26 27 21 15 11
result:
ok 6 numbers
Test #4:
score: 6
Accepted
time: 0ms
memory: 3748kb
input:
200 545371756 272685879 136342940 545371756 272685879 545371756 272685877 136342937 68171467 68171474 68171472 68171473 34085737 68171473 68171472 68171474 68171467 136342937 272685877 545371756 272685879 545371756 136342940 272685879 545371756 327464463 455363267 859187150 429593576 214796789 85918...
output:
27 36 25 26 16 11 15 21 19 22
result:
ok 10 numbers
Test #5:
score: 6
Accepted
time: 0ms
memory: 3588kb
input:
200 433494437 165580141 63245986 24157817 9227465 3524578 1346269 514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2 1 1 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 102334155 267914296 701408733 863735928 433494437 165580141 632459...
output:
5 13 5 5 8 5 13 5 5 6
result:
ok 10 numbers
Test #6:
score: 6
Accepted
time: 0ms
memory: 3816kb
input:
187 433494437 165580141 63245986 24157817 9227465 3524578 1346269 514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2 1 1 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 102334155 267914296 701408733 868260277 433494437 165580141 632459...
output:
4 36 18 10 19 11 3 29
result:
ok 8 numbers
Test #7:
score: 6
Accepted
time: 0ms
memory: 3824kb
input:
200 942616273 418940008 209470430 104734784 104734784 104735481 523675545 247785 701408733 267914296 102334155 39088169 14930352 5702887 2178309 832040 317811 121393 46368 17711 6765 2584 987 377 144 55 21 8 3 1 1 1 2 5 13 34 89 233 610 1597 4181 10946 28657 75025 196418 514229 1346269 3524578 92274...
output:
5 21 8 5 9 8 20 17 5 5
result:
ok 10 numbers
Test #8:
score: 6
Accepted
time: 0ms
memory: 3624kb
input:
200 641304094 22086510 5470810 2634455 1317187 658631 329083 126285 49415 22321 11410 5273 359 133 50 20 9 3 3 3 9 30 79 220 585 1226 2467 4851 27355 76469 202803 2836339 8307675 16614893 38701275 77401954 154804637 309608784 619217509 353775485 433494437 165580141 63245986 24157817 9227465 3524578 ...
output:
5 13 9 9 9 4 12 12 11 5
result:
ok 10 numbers
Test #9:
score: 6
Accepted
time: 0ms
memory: 3784kb
input:
200 433494437 165580141 63245986 24157817 9227465 3524578 1346269 514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2 1 1 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 102334155 267914296 701408733 693739790 701408733 267914296 102334...
output:
5 5 5 4 5 3 9 19 9 16
result:
ok 10 numbers
Test #10:
score: 6
Accepted
time: 0ms
memory: 3592kb
input:
200 811426933 198737194 91129973 45564654 22782332 6305563 3152428 1219185 505660 252621 43570 21857 11092 2766 1419 327 118 44 15 3 1 1 3 6 14 31 76 196 509 1034 4036 8138 52164 104730 208684 713957 1933360 8238658 16477615 107607533 306345216 612690552 5165 701408733 267914296 102334155 39088169 1...
output:
5 5 5 5 4 3 17 22 11 22
result:
ok 10 numbers
Test #11:
score: 6
Accepted
time: 0ms
memory: 3596kb
input:
170 81553716 641270070 76671075 423535716 81513969 349346472 918947671 643372070 434082866 664656456 639157656 473824723 263466558 960408345 313957771 754077653 952732710 111312524 68261315 315588907 511788074 951463287 402771182 51452283 4352857 86643186 343917032 740824934 31237226 361281509 99056...
output:
60 20 67 55 72 66 47 18
result:
ok 8 numbers
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 3620kb
input:
200 517847507 845063523 900782365 733754788 868260277 512811830 106915073 2556529 228137609 242594414 695501734 1446343 933668801 559293539 298824117 637105802 625215851 312386451 100447359 186927021 376963403 300653848 857052812 501599341 349295044 922104431 840182910 996573394 684887153 779348052 ...
output:
74 97 31 53 14 45 1 64 10 10
result:
wrong answer 7th numbers differ - expected: '2', found: '1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Test #59:
score: 32
Accepted
time: 192ms
memory: 4772kb
input:
185137 895278847 447639418 223819705 895278847 25847602 892542542 725274571 68345857 72124244 67050536 71135605 66549838 72378749 66083078 72261084 67667076 70423484 68942136 725274571 798132375 68764887 958288578 703862250 55104628 58120315 54690522 57110282 54279470 56516680 54581941 58474132 5445...
output:
59 26 80 55 43 41 79 37 57 79 69 29 31 25 26 76 32 25 27 36 34 39 67 40 67 71 45 40 49 52 64 61 29 40 39 34 41 19 28 51 31 43 62 23 31 26 73 39 63 36 53 27 46 56 30 67 60 37 71 22 42 59 67 87 16 27 20 38 14 64 20 19 41 34 55 53 15 51 43 29 71 60 49 9 76 18 86 29 73 61 38 46 21 62 20 20 67 71 83 82 5...
result:
ok 46660 numbers
Test #60:
score: 0
Time Limit Exceeded
input:
250000 667582288 333791140 166895569 667582288 99573823 970008947 834597000 12471817 12607290 12487687 12576099 12465363 12618633 12513272 12580300 12472038 12635499 12521112 12568109 12475947 12596996 12534373 12566264 12457253 12610586 12463726 12606038 12490882 12599220 12538123 12628955 12536981...
output:
result:
Subtask #5:
score: 0
Time Limit Exceeded
Test #76:
score: 29
Accepted
time: 177ms
memory: 4932kb
input:
235469 96936 48463 24226 96936 25951 73765 63933 7121 7884 7166 7731 7464 7559 7300 7767 7314 63933 88750 6093 115886 111307 16371 17529 15944 17376 16099 18186 15910 111307 116042 13997 111982 95565 10713 11748 10849 11375 11093 11406 10874 11810 11197 95565 98914 1302 65917 16473 32953 65917 15943...
output:
34 56 73 61 41 13 74 46 33 33 14 53 36 46 18 63 65 79 72 15 20 57 66 83 19 46 62 58 44 76 76 68 41 56 9 29 59 73 64 21 63 33 29 62 27 36 20 65 54 71 29 47 13 32 48 74 64 75 79 17 24 49 20 41 57 17 23 67 67 18 19 54 63 74 72 45 61 30 27 60 33 36 49 49 24 56 42 60 20 53 32 75 44 57 17 34 71 45 25 39 2...
result:
ok 44829 numbers
Test #77:
score: 0
Time Limit Exceeded
input:
250000 88054 44025 22011 88054 6068 106051 104212 1356 1371 1362 1370 1361 1371 1358 1371 1357 1364 1354 1367 1362 1371 1361 1365 1359 1363 1357 1370 1361 1366 1360 1363 1357 1369 1358 1367 1358 1371 1355 1371 1359 1371 1360 1370 1359 1371 1357 1363 1357 1370 1355 1371 1360 1366 1355 1368 1358 1364 ...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
0%