QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#449850#8597. Запити красот пiдмасивiвgreen_gold_dog#0 910ms349800kbC++206.8kb2024-06-21 18:17:422024-06-21 18:17:43

Judging History

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

  • [2024-06-21 18:17:43]
  • 评测
  • 测评结果:0
  • 用时:910ms
  • 内存:349800kb
  • [2024-06-21 18:17:42]
  • 提交

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 = 9'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;
	vector<ll> m;
	ll size;
	segment_tree_min(ll n) {
		size = 1;
		while (size < n) {
			size *= 2;
		}
		tree.resize(size * 2, make_pair(0, 0));
		m.resize(size * 2, 0);
		for (ll i = 0; i < size; i++) {
			tree[i + size].second = i;
		}
	}
	pair<ll, ll> add(ll v, ll x) {
		tree[v].first += x;
		m[v] += x;
		return tree[v];
	}
	void push(ll v) {
		add(v * 2, m[v]);
		add(v * 2 + 1, m[v]);
		m[v] = 0;
	}
	void add(ll l, ll r, ll x) {
		add(1, 0, size, l, r, x);
	}
	pair<ll, ll> add(ll v, ll l, ll r, ll ql, ll qr, ll x) {
		if (ql <= l && r <= qr) {
			return add(v, x);
		}
		if (qr <= l || r <= ql) {
			return tree[v];
		}
		push(v);
		ll mid = (l + r) / 2;
		return tree[v] = min(add(v * 2, l, mid, ql, qr, x), add(v * 2 + 1, mid, r, ql, qr, x));
	}
	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);
		}
		push(v);
		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;
	vector<ll> m;
	ll size;
	segment_tree_max(ll n) {
		size = 1;
		while (size < n) {
			size *= 2;
		}
		tree.resize(size * 2, make_pair(0, 0));
		m.resize(size * 2, 0);
		for (ll i = 0; i < size; i++) {
			tree[i + size].second = i;
		}
	}
	pair<ll, ll> add(ll v, ll x) {
		tree[v].first += x;
		m[v] += x;
		return tree[v];
	}
	void push(ll v) {
		add(v * 2, m[v]);
		add(v * 2 + 1, m[v]);
		m[v] = 0;
	}
	void add(ll l, ll r, ll x) {
		add(1, 0, size, l, r, x);
	}
	pair<ll, ll> add(ll v, ll l, ll r, ll ql, ll qr, ll x) {
		if (ql <= l && r <= qr) {
			return add(v, x);
		}
		if (qr <= l || r <= ql) {
			return tree[v];
		}
		push(v);
		ll mid = (l + r) / 2;
		return tree[v] = max(add(v * 2, l, mid, ql, qr, x), add(v * 2 + 1, mid, r, ql, qr, x));
	}
	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);
		}
		push(v);
		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]);
	}
	segment_tree_min stmi(n);
	segment_tree_max stma(n);
	vector<pair<ll, ll>> jmi(n), jma(n);
	vector<vector<ll>> pbinup(n + 1, vector<ll>(LOG, n));
	vector<vector<ll>> pbinupc(n + 1, vector<ll>(LOG, INF64));
	vector<vector<ll>> pbinupminp(n + 1, vector<ll>(LOG, INF64));
	vector<vector<ll>> pbinupmaxp(n + 1, vector<ll>(LOG, -INF64));
	vector<vector<ll>> mbinup(n + 1, vector<ll>(LOG, n));
	vector<vector<ll>> mbinupc(n + 1, vector<ll>(LOG, INF64));
	vector<vector<ll>> mbinupminp(n + 1, vector<ll>(LOG, INF64));
	vector<vector<ll>> mbinupmaxp(n + 1, vector<ll>(LOG, -INF64));
	for (ll i = n - 1; i >= 0; i--) {
		stmi.add(i, n, arr[i]);
		stma.add(i, n, arr[i]);
		jmi[i] = stmi.get(i, n);
		jma[i] = stma.get(i, n);
		jmi[i].second++;
		jma[i].second++;
		pbinup[i][0] = jma[i].second;
		pbinupc[i][0] = jma[i].first;
		pbinupminp[i][0] = ps[i];
		pbinupmaxp[i][0] = ps[pbinup[i][0]];
		mbinup[i][0] = jmi[i].second;
		mbinupc[i][0] = -jmi[i].first;
		mbinupmaxp[i][0] = ps[i];
		mbinupminp[i][0] = ps[mbinup[i][0]];
		{
			ll j = 1;
			pbinup[i][j] = mbinup[pbinup[i][j - 1]][j - 1];
			pbinupc[i][j] = min(mbinupc[pbinup[i][j - 1]][j - 1], pbinupc[i][j - 1]);
			pbinupminp[i][j] = min(mbinupminp[pbinup[i][j - 1]][j - 1], pbinupminp[i][j - 1]);
			pbinupmaxp[i][j] = max(mbinupmaxp[pbinup[i][j - 1]][j - 1], pbinupmaxp[i][j - 1]);
			mbinup[i][j] = pbinup[mbinup[i][j - 1]][j - 1];
			mbinupc[i][j] = min(pbinupc[mbinup[i][j - 1]][j - 1], mbinupc[i][j - 1]);
			mbinupminp[i][j] = min(pbinupminp[mbinup[i][j - 1]][j - 1], mbinupminp[i][j - 1]);
			mbinupmaxp[i][j] = max(pbinupmaxp[mbinup[i][j - 1]][j - 1], mbinupmaxp[i][j - 1]);
		}
		for (ll j = 2; j < LOG; j++) {
			pbinup[i][j] = pbinup[pbinup[i][j - 1]][j - 1];
			pbinupc[i][j] = min(pbinupc[pbinup[i][j - 1]][j - 1], pbinupc[i][j - 1]);
			pbinupminp[i][j] = min(pbinupminp[pbinup[i][j - 1]][j - 1], pbinupminp[i][j - 1]);
			pbinupmaxp[i][j] = max(pbinupmaxp[pbinup[i][j - 1]][j - 1], pbinupmaxp[i][j - 1]);
			mbinup[i][j] = mbinup[mbinup[i][j - 1]][j - 1];
			mbinupc[i][j] = min(mbinupc[mbinup[i][j - 1]][j - 1], mbinupc[i][j - 1]);
			mbinupminp[i][j] = min(mbinupminp[mbinup[i][j - 1]][j - 1], mbinupminp[i][j - 1]);
			mbinupmaxp[i][j] = max(mbinupmaxp[mbinup[i][j - 1]][j - 1], mbinupmaxp[i][j - 1]);
		}
	}
	for (ll i = 0; i < q; i++) {
		ll t, l, r;
		cin >> t >> l >> r;
		if (t == 1) {
			r = n - r;
			l = n - l;
			l++;
			swap(l, r);
			ll nl = 0, nr = INF64;
			while (nr - nl > 1) {
				ll mid = (nl + nr) / 2;
				ll vm = l, vp = l;
				ll mminp = ps[l], mmaxp = ps[l];
				ll pminp = ps[l], pmaxp = ps[l];
				for (ll j = LOG - 1; j >= 0; j--) {
					if (mbinup[vm][j] < r && mbinupc[vm][j] >= mid) {
						assign_min(mminp, mbinupminp[vm][j]);
						assign_max(mmaxp, mbinupmaxp[vm][j]);
						vm = mbinup[vm][j];
					}
					if (pbinup[vp][j] < r && pbinupc[vp][j] >= mid) {
						assign_min(pminp, pbinupminp[vp][j]);
						assign_max(pmaxp, pbinupmaxp[vp][j]);
						vp = pbinup[vp][j];
					}
				}
				if (max(max(ps[r] - mminp, mmaxp - ps[r]), max(ps[r] - pminp, pmaxp - ps[r])) >= mid) {
					nl = mid;
				} else {
					nr = mid;
				}
			}
			cout << nl << '\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: 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: 4ms
memory: 5240kb

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
2003856312
7251185652
2554989078
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 2nd numbers differ - expected: '7971661681', found: '2003856312'

Subtask #3:

score: 0
Wrong Answer

Test #14:

score: 0
Wrong Answer
time: 910ms
memory: 349736kb

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:

wrong answer 52nd numbers differ - expected: '123800915687', found: '82061951235'

Subtask #4:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 817ms
memory: 349800kb

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: 870ms
memory: 349648kb

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:

1
7
8
6
8
4
3
7
9
9
5
9
6
6
9
3
8
1
8
3
6
6
4
7
6
4
3
2
8
5
6
3
5
5
3
7
5
1
7
5
9
5
8
0
5
7
6
8
5
5
6
2
3
6
6
8
4
6
9
4
6
3
6
5
8
6
6
5
5
9
8
4
7
6
4
5
6
2
3
7
4
5
4
4
6
7
9
1
2
9
3
4
5
1
9
3
2
4
9
4
7
2
9
7
8
1
8
8
5
6
8
8
3
6
5
3
6
5
9
6
6
8
1
5
8
4
5
3
7
4
10
2
5
5
6
8
2
2
6
4
6
8
6
5
0
8
7
2
3
7...

result:

wrong answer 1st numbers differ - expected: '9', found: '1'

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%