QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #449587 | #8597. Запити красот пiдмасивiв | Qwerty1232# | 14 | 212ms | 3620kb | C++23 | 1.0kb | 2024-06-21 15:02:08 | 2024-06-21 15:02:10 |
Judging History
answer
#include <bits/stdc++.h>
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<int> input(n);
for (auto& i : input) {
std::cin >> i;
}
std::vector<int64_t> prf(n + 1);
for (int i = 0; i < n; i++) {
prf[i + 1] = prf[i] + input[i];
}
std::vector<int64_t> dp(n + 1);
for (int i = 0; i < q; i++) {
int tp;
std::cin >> tp;
if (tp == 1) {
int l, r;
std::cin >> l >> r;
l--;
std::fill(dp.begin() + l, dp.begin() + r + 1, 0);
dp[l] = 1e18;
for (int i = l; i < r; i++) {
for (int j = i + 1; j <= r; j++) {
dp[j] = std::max(dp[j], std::min(dp[i], std::abs(prf[j] - prf[i])));
}
}
int64_t ans = dp[r];
std::cout << ans << "\n";
} else {
assert(false);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
1000000 1000000 548734664 631285694 511074814 185066089 177199147 524740185 143108778 954318193 103939390 194933972 126964310 977448144 188825490 775722231 460775045 254691982 436971964 566341931 148211711 74910105 923734998 440021758 474275150 717904448 680353276 612974499 712145218 300908726 34722...
output:
result:
Subtask #2:
score: 14
Accepted
Test #7:
score: 14
Accepted
time: 212ms
memory: 3616kb
input:
1000 1000 -873807720 -737050877 797489760 406646247 -750849890 -581119106 43724194 -931326234 -9389547 -684003608 -926307185 -502569356 -461635706 -238087464 -83909772 -884633970 46721429 -576741985 -323890970 -855342249 -736506813 336516318 -4075924 -782227362 56799828 290931118 -471600723 81594380...
output:
9772834244 7971661681 7251185652 5902581650 12301584130 9137214347 10770040139 9693548841 12636393268 9951777555 8590138425 9126178404 8438322412 10469973494 9585010202 12336530829 12305905331 12818655084 9576894451 9228532410 10060968297 12060843219 8619457836 8862797014 12336530829 6408306273 9621...
result:
ok 1000 numbers
Test #8:
score: 0
Accepted
time: 208ms
memory: 3556kb
input:
1000 1000 692134706 979271447 980370950 994825542 999242327 999523358 999690467 999798408 999882013 999922869 -922596273 -659587774 640420971 986220997 990730649 999401779 999536875 999723478 999763458 999904584 42593372 653970020 930711142 994805382 996905450 997728548 998747773 999933140 999961560...
output:
508001236169 455677156350 464108965476 458984106243 591329464196 544306954522 606712940905 670216620925 467826054462 364402607562 478731198606 441359828061 589114661689 350571309943 538138574474 488313052986 406263573994 550962494917 490268630633 620941260144 452889284903 484667815820 398698987974 3...
result:
ok 1000 numbers
Test #9:
score: 0
Accepted
time: 200ms
memory: 3620kb
input:
1000 1000 580673741 925261058 993980536 997024573 999941913 999972191 999980883 999989783 999992331 999997282 999999063 999999150 999999272 999999338 999999726 999999825 999999870 999999902 999999977 999999989 999999993 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 ...
output:
560539190835 333464742334 628653998632 212079705817 586450009464 766145951766 886930541461 563384169825 438655875762 409072137159 571287452742 482618339702 532034732041 549824903600 640044000756 465785253221 406176201314 846137019311 349834504581 788697842607 451633268981 735398048343 645352016986 4...
result:
ok 1000 numbers
Test #10:
score: 0
Accepted
time: 209ms
memory: 3580kb
input:
1000 1000 113778409 616366980 758104758 774066845 884853572 946156080 949750283 973895123 986390312 994415418 998589686 998642039 999864578 999874539 999920293 999965949 999983998 999992235 999997899 999999234 999999892 999999964 999999978 999999980 999999995 999999999 999999999 1000000000 100000000...
output:
754778196417 695488349209 630480332057 412195393475 782679791114 602689765616 503897653789 488317363014 302782338384 348428051191 752051131798 432518915969 598010108356 663033550477 814335749262 318055380779 445729163692 336288091592 757027035466 821717471601 781958862262 718420655430 423109373010 7...
result:
ok 1000 numbers
Test #11:
score: 0
Accepted
time: 207ms
memory: 3508kb
input:
1000 1000 -353116922 418563102 940826827 988264316 988338236 996408365 999853601 999974320 999993971 999995926 999998121 999999678 999999755 999999806 999999971 999999972 999999984 999999991 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000...
output:
590373117158 732187641017 435372856316 652987578737 733292717761 248304131475 670498858492 259638664362 403406869931 653650856372 852594123641 787243880579 516800698532 428096472909 635223223388 485889309952 727613089170 694882124799 494270857759 434790317099 670088269609 797171569331 631514600863 5...
result:
ok 1000 numbers
Test #12:
score: 0
Accepted
time: 206ms
memory: 3620kb
input:
1000 1000 -221488095 587209633 872267838 890515934 994766025 997079143 998735303 998996787 999170582 999355457 999852598 999940425 999957014 999974875 999983770 999986290 999988558 999994493 999996741 999996805 999999341 999999837 999999856 999999954 999999972 999999976 999999987 999999999 100000000...
output:
622373476144 402153598108 672162651572 646493759749 595493759749 638404656027 692351281790 641769593147 748629283376 776968313017 699353081713 656395292200 334279316100 577911508843 812968313017 433174756274 514589630792 762110228713 321037336729 524645635375 823968313017 675363780989 764534665675 5...
result:
ok 1000 numbers
Test #13:
score: 0
Accepted
time: 208ms
memory: 3556kb
input:
1000 1000 -362722497 324046604 660730013 792835785 960138764 986476487 991231845 999524667 999598449 999843840 999869223 999914357 999934988 999969083 999972358 999998373 999999245 999999467 999999499 999999898 999999971 999999975 999999977 999999995 1000000000 1000000000 1000000000 1000000000 10000...
output:
382332552370 686345331368 424430112355 916112024283 630730004870 308325992400 438430299259 528912353216 896112024283 553216242505 661345331369 139766693095 447227200512 825112024283 799033892170 602150204024 524734124402 300625915893 438377837722 423712731278 557790198467 655345331368 802033892170 8...
result:
ok 1000 numbers
Subtask #3:
score: 0
Time Limit Exceeded
Test #14:
score: 0
Time Limit Exceeded
input:
200000 200000 580139218 -783262026 565291185 -701435432 -591602198 -342573855 -900284959 -10919966 -682899137 -282058183 963121871 491072571 691886927 761414760 -828585515 888361166 -790814084 145385324 214735368 388759807 -80339362 -975535748 522135695 301673442 36714481 785639770 319723485 1098009...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #21:
score: 0
Time Limit Exceeded
input:
200000 200000 128744308 920701830 -482412021 59142239 721167306 -622861403 165749748 -449445968 -760679479 -207234657 171482190 -239316743 75518499 -717652242 502074875 -731242646 -183939818 -625333917 -53052313 185734819 -780000096 -563390882 -690210905 596581513 764466021 776717157 -38544163 -7898...
output:
128744308 1049446138 567034117 626176356 1347343662 724482259 890232007 906557623 1347343662 1347343662 1347343662 1347343662 1347343662 1347343662 1347343662 1466264164 1650203982 2275537899 2328590212 2142855393 2922855489 3486246371 4176457276 3579875763 2815409742 2137764691 2099220528 286704480...
result:
Subtask #5:
score: 0
Time Limit Exceeded
Test #28:
score: 0
Time Limit Exceeded
input:
200000 200000 3 -5 -3 3 3 -5 7 -2 2 -4 -4 9 0 -4 -2 2 -5 7 -2 3 -8 1 6 -7 9 -3 -2 4 -2 -2 3 -2 1 0 -3 6 0 -6 -2 6 -5 6 -4 3 2 -4 5 -2 -8 1 1 2 1 -3 3 5 -9 1 3 -2 0 1 -2 1 2 5 -1 -4 -1 -3 7 -7 7 1 -6 7 -1 -5 1 4 -7 6 -3 -4 -1 4 1 5 -7 -3 9 1 -6 2 -3 1 6 -1 -1 1 -1 -5 -3 9 -5 4 -1 3 -2 -4 -4 8 1 0 -9 ...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #6:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
0%