QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#449895 | #8597. Запити красот пiдмасивiв | green_gold_dog# | 14 | 1835ms | 110268kb | C++20 | 3.9kb | 2024-06-21 18:53:29 | 2024-06-21 18:53:29 |
Judging History
answer
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 1'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007, LOG = 21;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) const {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
struct segment_tree_min {
vector<pair<ll, ll>> tree;
ll size;
segment_tree_min(vector<ll> arr) {
size = 1;
while (size < arr.size()) {
size *= 2;
}
tree.resize(size * 2, make_pair(0, 0));
arr.resize(size, INF64);
for (ll i = 0; i < size; i++) {
tree[i + size].second = i;
tree[i + size].first = arr[i];
}
for (ll i = size - 1; i > 0; i--) {
tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
}
}
pair<ll, ll> get(ll l, ll r) {
return get(1, 0, size, l, r);
}
pair<ll, ll> get(ll v, ll l, ll r, ll ql, ll qr) {
if (ql <= l && r <= qr) {
return tree[v];
}
if (qr <= l || r <= ql) {
return make_pair(INF64, 0);
}
ll mid = (l + r) / 2;
return min(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr));
}
};
struct segment_tree_max {
vector<pair<ll, ll>> tree;
ll size;
segment_tree_max(vector<ll> arr) {
size = 1;
while (size < arr.size()) {
size *= 2;
}
tree.resize(size * 2, make_pair(0, 0));
arr.resize(size, -INF64);
for (ll i = 0; i < size; i++) {
tree[i + size].second = i;
tree[i + size].first = arr[i];
}
for (ll i = size - 1; i > 0; i--) {
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
}
pair<ll, ll> get(ll l, ll r) {
return get(1, 0, size, l, r);
}
pair<ll, ll> get(ll v, ll l, ll r, ll ql, ll qr) {
if (ql <= l && r <= qr) {
return tree[v];
}
if (qr <= l || r <= ql) {
return make_pair(-INF64, 0);
}
ll mid = (l + r) / 2;
return max(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr));
}
};
void solve() {
ll n, q;
cin >> n >> q;
vector<ll> arr(n);
vector<ll> ps(1, 0);
for (ll i = 0; i < n; i++) {
cin >> arr[i];
}
reverse(arr.begin(), arr.end());
for (ll i = 0; i < n; i++) {
ps.push_back(ps.back() + arr[i]);
}
vector<ll> ps2 = ps;
ps2.erase(ps2.begin());
segment_tree_min stmi(ps2);
segment_tree_max stma(ps2);
for (ll i = 0; i < q; i++) {
ll t, l, r;
cin >> t >> l >> r;
if (t == 1) {
l = n - l;
r = n - r;
l++;
swap(l, r);
ll ans = abs(ps[r] - ps[l]);
ll nx = INF64;
ll ni = l;
bool b = false;
while (ni < r) {
if (b) {
auto[mi, ind] = stmi.get(ni, r);
mi -= ps[ni];
assign_min(nx, abs(mi));
ni = ind + 1;
} else {
auto[mi, ind] = stma.get(ni, r);
mi -= ps[ni];
assign_min(nx, abs(mi));
ni = ind + 1;
}
assign_max(ans, min(nx, abs(ps[r] - ps[ni])));
b = !b;
}
b = true;
nx = INF64;
ni = l;
while (ni < r) {
if (b) {
auto[mi, ind] = stmi.get(ni, r);
mi -= ps[ni];
assign_min(nx, abs(mi));
ni = ind + 1;
} else {
auto[mi, ind] = stma.get(ni, r);
mi -= ps[ni];
assign_min(nx, abs(mi));
ni = ind + 1;
}
assign_max(ans, min(nx, abs(ps[r] - ps[ni])));
b = !b;
}
cout << ans << '\n';
} else {
exit(1);
}
}
}
int main() {
if (IS_FILE) {
freopen("", "r", stdin);
freopen("", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
if (IS_TEST_CASES) {
cin >> t;
}
for (ll i = 0; i < t; i++) {
solve();
}
}
詳細信息
Subtask #1:
score: 4
Accepted
Test #1:
score: 4
Accepted
time: 1818ms
memory: 110244kb
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:
ok 1000000 numbers
Test #2:
score: 0
Accepted
time: 1835ms
memory: 109588kb
input:
1000000 1000000 990113895 993892498 998227668 999901378 999927530 999967151 999984400 999995999 999997829 999997900 999998862 999999773 999999868 999999949 999999971 999999980 999999984 999999997 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 10000...
output:
517388975548697 583250844300324 432944007956879 651986171831501 542238696573424 441761501786754 330123013631473 870241324122629 883396218117077 408105370042427 707816626704213 508232505211911 739818893951077 766666985527682 465224901247448 886122292332962 914658373213235 421779818564551 727905274312...
result:
ok 1000000 numbers
Test #3:
score: 0
Accepted
time: 1814ms
memory: 109856kb
input:
1000000 1000000 141598548 830665328 993488224 999755561 999945155 999986513 999989333 999990586 999994476 999997209 999998165 999998359 999998707 999999473 999999852 999999930 999999938 999999963 999999965 999999981 999999996 999999998 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...
output:
356173976182880 480636735678882 715649266153211 296099114480174 495577657145300 880164857057696 360829708390397 893190933168525 659770218871691 260229819810974 825160619301796 709264679095607 588830530083195 520438551091261 655451391395164 578240261246493 212576955707985 725338244461847 416476415692...
result:
ok 1000000 numbers
Test #4:
score: 0
Accepted
time: 1798ms
memory: 109324kb
input:
1000000 1000000 777974618 985268992 996078973 997554180 997788695 999658168 999968830 999980473 999998143 999999812 999999826 999999905 999999953 999999974 999999990 999999992 999999996 999999998 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000...
output:
614388727692563 649626175674650 200543340460644 429537231405728 430189231405728 716472378936104 565372458226305 594699593996257 564844859199650 644148647862746 747289687203253 561010517064553 468050674466851 357068282778875 437757064198385 414636189013152 380245538829532 598461229740399 261190443589...
result:
ok 1000000 numbers
Test #5:
score: 0
Accepted
time: 1806ms
memory: 109220kb
input:
1000000 1000000 377309365 894144488 921143445 991660683 995450636 995556635 999173866 999401820 999822658 999976711 999993812 999999725 999999817 999999968 999999992 999999996 999999998 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 10000...
output:
650552155322823 369803954654729 813016884061089 583669437559348 846050884061089 891397884061089 597163155322823 501082437559348 407475954654729 745849437559348 777099884061089 766289884061089 246508728738266 779717884061089 575586954654729 748072437559348 470318708821082 417518708821082 323575954654...
result:
ok 1000000 numbers
Test #6:
score: 0
Accepted
time: 1796ms
memory: 110268kb
input:
1000000 1000000 607026608 839552936 931303147 946375702 979264955 989112811 991854785 994078939 997321934 997703417 999932023 999934524 999987158 999987867 999996003 999996883 999997617 999998635 999999062 999999992 999999995 999999997 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...
output:
403158000000000 716622000000000 582130000000000 452232000000000 773107000000000 671339000000000 640401000000000 402688000000000 341097000000000 373220000000000 382028000000000 476739000000000 764869000000000 443808000000000 790093000000000 650563000000000 824479000000000 667243000000000 796546000000...
result:
ok 1000000 numbers
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 2ms
memory: 3768kb
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 157th numbers differ - expected: '5770941622', found: '5075319683'
Subtask #3:
score: 10
Accepted
Test #14:
score: 10
Accepted
time: 924ms
memory: 28132kb
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:
ok 200000 numbers
Test #15:
score: 0
Accepted
time: 309ms
memory: 28972kb
input:
200000 200000 216963970 895963907 970921505 973720179 985811250 998640537 999103413 999661484 999729609 999942450 -821783874 781997309 829131735 832477333 892292610 985929024 998231319 999101470 999204347 999373872 473465706 768624229 994843197 999760281 999881158 999973657 999988928 999993358 99999...
output:
112621847444942 101030183697291 63233054628753 80384063266952 115039837711512 95578572948651 143407295417810 60640420205729 72326537106317 97513628293662 111552624754764 88836367993245 60834804129630 81553727338901 100409741576180 65344377179665 95711093922326 112060888712228 73442129454981 65507735...
result:
ok 200000 numbers
Test #16:
score: 0
Accepted
time: 290ms
memory: 29080kb
input:
200000 200000 -824647563 -226311394 73090714 76436719 759867982 803623373 829644660 946127786 957102501 987106779 997539215 999943331 999979160 999991880 999996009 999997678 999999024 999999063 999999274 999999406 999999496 999999684 999999952 999999985 999999992 999999993 999999996 999999998 999999...
output:
107254718306887 59985268718865 160651387958961 113576472431692 94922328063875 159793953406254 103324138822766 134824989111115 123862745746950 169491678824442 91501549032165 99093005632887 139347712481764 122330217459374 84161090195491 89777898364239 162149696406419 120396086999264 88322334520469 615...
result:
ok 200000 numbers
Test #17:
score: 0
Accepted
time: 284ms
memory: 28704kb
input:
200000 200000 -282183530 -94945479 227825325 604182067 992536174 995235520 999623224 999831612 999944208 999969121 999974356 999980957 999988940 999994107 999995968 999998154 999999531 999999584 999999922 999999935 999999969 999999985 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000...
output:
123377619867900 100211431195321 145963538594998 190203444064019 64843966674700 77549625539887 184560557631975 39023969105634 110224991478919 60057393127515 82953877723644 86412104386226 160532783809484 121422800259115 193867540418057 93054646076494 162102767313085 35476495087574 102656767657861 8893...
result:
ok 200000 numbers
Test #18:
score: 0
Accepted
time: 287ms
memory: 27860kb
input:
200000 200000 895486773 904267709 971843319 989242035 997432691 998747539 999923993 999958496 999981782 999997130 999998160 999999003 999999967 999999992 999999996 999999997 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000...
output:
107947399476523 162249388524327 188244246063420 149188588881854 157732011675993 143224891836264 133208454676491 163999809906499 141125758850610 129080307951204 119938099343301 102187458820136 42426020657946 113901944910560 54823208026881 147838531324875 119767412026628 157136338370764 34461988892014...
result:
ok 200000 numbers
Test #19:
score: 0
Accepted
time: 297ms
memory: 27916kb
input:
200000 200000 15691546 982710368 991752623 996635863 999985515 999992516 999995094 999999596 999999991 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...
output:
72523839838926 125348292306559 156051487951881 110134134212103 157069281441772 82917291584024 119805834008914 161199487951881 118949623834329 129858684120921 104031770661480 135286708593556 136516858580023 60306452467633 70864365507686 134657502564275 83413848621308 164520131445345 125642684120921 1...
result:
ok 200000 numbers
Test #20:
score: 0
Accepted
time: 275ms
memory: 28100kb
input:
200000 200000 -90259554 929646040 932381231 965326126 992162797 999519149 999868148 999979048 999996345 999998606 999999942 999999998 999999998 999999999 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000...
output:
165849002394680 130735002394680 156026002394680 127391002394680 107616002394680 119917002394680 68572000000000 125579002394680 168319002394680 145634002394680 124946002394680 120901002394680 151983002394680 118365002394680 134173002394680 77681002394680 117765002394680 126867002394680 12318900239468...
result:
ok 200000 numbers
Subtask #4:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 612ms
memory: 28748kb
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:
wrong answer 71st numbers differ - expected: '3002133635', found: '2435794510'
Subtask #5:
score: 0
Wrong Answer
Test #28:
score: 0
Wrong Answer
time: 547ms
memory: 28104kb
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:
9 7 8 7 8 6 5 7 9 9 7 9 6 6 9 6 8 9 9 5 6 6 5 7 6 6 5 7 8 6 6 7 5 6 7 7 5 9 7 6 9 5 8 10 5 8 6 8 5 5 8 7 7 6 6 8 4 6 9 7 7 5 6 5 8 6 6 5 5 9 8 5 7 6 7 7 6 6 5 7 6 5 6 6 6 7 9 9 8 9 7 6 6 9 9 7 8 5 9 4 7 8 9 8 9 9 8 8 5 6 8 8 4 6 6 6 6 5 9 6 6 8 9 5 9 6 6 5 7 5 10 7 5 5 6 8 6 8 7 5 6 8 6 5 10 8 8 6 6...
result:
wrong answer 22nd numbers differ - expected: '7', found: '6'
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #6:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%