QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #449631 | #8597. Запити красот пiдмасивiв | bashkort# | 0 | 2ms | 3624kb | C++20 | 2.1kb | 2024-06-21 15:32:02 | 2024-06-21 15:32:04 |
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
auto rangeSum = [&](int l, int r) {
return accumulate(a.begin() + l, a.begin() + r, 0LL);
};
auto prefMinMax = [&](int l, int r) -> pair<int, int> {
ll pmin = 0, pmax = 0;
int imin = l, imax = l;
ll sum = 0;
for (int i = l; i < r; ++i) {
sum += a[i];
if (pmin > sum) {
pmin = sum;
imin = i + 1;
}
if (pmax < sum) {
pmax = sum;
imax = i + 1;
}
}
return {imin, imax};
};
auto sufMinMax = [&](int l, int r) -> pair<int, int> {
ll pmin = 0, pmax = 0;
int imin = r, imax = r;
ll sum = 0;
for (int i = r - 1; i >= l; --i) {
sum += a[i];
if (pmin > sum) {
pmin = sum;
imin = i;
}
if (pmax < sum) {
pmax = sum;
imax = i;
}
}
return {imin, imax};
};
auto query = [&](int l, int r) -> ll {
ll ans = abs(rangeSum(l, r)); // 1 block
auto [imin, imax] = prefMinMax(l, r);
for (int p : {imin, imax}) {
ans = max(ans, min(abs(rangeSum(l, p)), abs(rangeSum(p, r))));
auto [x, y] = sufMinMax(p, r);
for (int t : {x, y}) {
ans = max(ans, min({abs(rangeSum(l, p)), abs(rangeSum(p, t)), abs(rangeSum(t, r))}));
}
}
return ans;
};
auto modify = [&](int i, int x) {
a[i] = x;
};
while (q--) {
int type, l, r;
cin >> type >> l >> r;
if (type == 1) {
cout << query(l - 1, r) << '\n';
} else {
modify(l - 1, r);
}
}
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:
251801387395338 230985543990378 233364582761908 165509624203582 383254838720986 448483728625094 365779189638223 259921744673457 396032911262151 463175787332481 396490494773605 379294045009719 380905359946099 248640668979163 372751657582612 250611799614193 382671202614963 249747705028859 377678676465...
result:
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 2ms
memory: 3624kb
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:
wrong answer 145th numbers differ - expected: '4486393352', found: '4374282936'
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:
351460487491 210343422436 312498498649 203192986383 287815765786 245818714404 213968420688 159327542896 169009698075 212975612931 197610853645 255310400798 318802499824 292657635865 313528174745 321957839407 262317902055 187559666100 220264896012 221468083688 294234309666 310907237863 189575747002 1...
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%