QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#524753 | #6337. Mizuyokan 2 | Qwerty1232# | 0 | 423ms | 5236kb | C++23 | 1.7kb | 2024-08-20 04:22:15 | 2024-08-20 04:22:16 |
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, -1e8);
dp[0] = 1;
constexpr int K = 35;
for (int i = 0; i < 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: 0ms
memory: 3556kb
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: 0ms
memory: 3508kb
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: 3552kb
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: 3556kb
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: 0
Wrong Answer
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 863735928 433494437 165580141 632459...
output:
4 12 4 5 8 5 13 5 5 6
result:
wrong answer 1st numbers differ - expected: '5', found: '4'
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: 100ms
memory: 4788kb
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: 32
Accepted
time: 420ms
memory: 5212kb
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:
479 432 209 299 73 389 201 103 301 236 132 294 176 319 309 76 223 90 292 372 428 240 403 469 459 298 330 139 178 264 119 140 215 116 231 90 412 284 131 272 101 103 400 413 410 403 94 165 115 157 134 443 128 125 239 297 140 283 111 409 430 224 112 194 279 224 410 414 275 110 282 285 168 146 216 318 2...
result:
ok 50000 numbers
Test #61:
score: 0
Time Limit Exceeded
input:
250000 686918541 343459266 171729631 686918541 162600005 909519391 751917777 1531698 1533456 1531623 1534143 1532545 1533883 1531702 1533707 1532628 1533520 1532278 1533729 1531461 1534213 1531804 1532982 1531815 1532983 1532627 1534082 1532622 1533761 1531583 1533895 1532427 1533015 1532299 1533382...
output:
3543 1850 1040 1576 2987 3193 1551 1318 3629 1026 2588 756 2167 3104 2934 2232 2279 961 2073 811 2729 2236 1198 2875 3166 1205 924 1942 2610 1286 3039 1881 953 864 3285 3160 1722 2892 1046 2827 1211 721 689 2659 2676 2659 2569 2931 2691 730 2489 1744 2854 1273 2449 1871 2381 1446 1191 1685 1864 3156...
result:
Subtask #5:
score: 0
Time Limit Exceeded
Test #76:
score: 29
Accepted
time: 95ms
memory: 4980kb
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: 29
Accepted
time: 423ms
memory: 5236kb
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:
146 118 301 455 177 65 187 177 317 351 366 219 382 117 178 136 157 405 245 166 285 271 202 376 120 97 326 95 369 194 221 167 206 73 197 372 117 237 176 128 69 101 449 215 261 410 85 169 257 312 285 297 227 181 423 298 205 371 416 343 301 406 122 335 296 222 190 365 429 433 205 389 223 227 281 357 16...
result:
ok 50000 numbers
Test #78:
score: 0
Time Limit Exceeded
input:
250000 107093 53547 26774 107093 53547 107093 53545 26771 13384 13391 13389 13390 6696 13390 13389 13391 13384 26771 53545 107093 53547 107093 26774 53547 107093 58591 28809 92235 46118 23060 92235 46118 92235 46116 23057 11527 11533 11531 11532 5767 11532 11531 11533 11527 23057 46116 92235 46118 9...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
0%