QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#449895#8597. Запити красот пiдмасивiвgreen_gold_dog#14 1835ms110268kbC++203.9kb2024-06-21 18:53:292024-06-21 18:53:29

Judging History

你现在查看的是最新测评结果

  • [2024-06-21 18:53:29]
  • 评测
  • 测评结果:14
  • 用时:1835ms
  • 内存:110268kb
  • [2024-06-21 18:53:29]
  • 提交

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%