oj.uz

Submission #797149

# Submission time Handle Problem Language Result Execution time Memory
797149 2023-07-29T07:20:33 Z Sohsoh84 Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 52428 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define int			ll
#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 5e5 + 10;
const ll INF = 8e18;

int FL[MAXN], FR[MAXN], A[MAXN], n, q, ans[MAXN];
vector<int> L_vec[MAXN];
vector<pll> QL[MAXN];

namespace segment {
	ll lz[MAXN << 2], sg[MAXN << 2], tof[MAXN << 2];
	
	void build(int l = 1, int r = n, int v = 1) {
		if (l == r) sg[v] = A[l];
		else {
			int mid = (l + r) >> 1;
			build(l, mid, v << 1);
			build(mid + 1, r, v << 1 | 1);
			sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
		}
	}

	inline void push(int v) { // be sure that tof[v] != -1
		if (lz[v] == 0) return;
		if (lz[v] > tof[v]) {
			sg[v] += lz[v] - tof[v];
			tof[v] = lz[v];

			lz[v << 1] = max(lz[v << 1], lz[v]);
			lz[v << 1 | 1] = max(lz[v << 1 | 1], lz[v]);
		}

		lz[v] = 0;
	}

	void update(int ql, int qr, ll val, int l = 1, int r = n, int v = 1) {
		push(v);
		if (ql > r || qr < l) return;
		if (ql <= l && qr >= r && tof[v] != -1) {
			lz[v] += val;
			push(v);
			return;
		}

		int mid = (l + r) >> 1;
		update(ql, qr, val, l, mid, v << 1);
		update(ql, qr, val, mid + 1, r, v << 1 | 1);

		tof[v] = (tof[v << 1] == tof[v << 1 | 1] ? tof[v << 1] : -1);
		sg[v] = max(sg[v << 1], sg[v << 1 | 1]);	
	}

	ll query(int ql, int qr, int l = 1, int r = n, int v = 1) {
		push(v);
		if (ql > r || qr < l) return -INF;
		if (ql <= l && qr >= r) return sg[v];

		int mid = (l + r) >> 1;
		return max(query(ql, qr, l, mid, v << 1),
				query(ql, qr, mid + 1, r, v << 1 | 1));
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> A[i];
	
	for (int i = 1; i <= n; i++)
		for (FL[i] = i - 1; FL[i] && A[FL[i]] < A[i]; FL[i] = FL[FL[i]]);

	for (int i = n; i > 0; i--)
		for (FR[i] = i + 1; FR[i] <= n && A[FR[i]] < A[i]; FR[i] = FR[FR[i]]);

	for (int i = 1; i <= n; i++) {
		if (FL[i] > 0) L_vec[FL[i]].push_back(i);
		if (FR[i] <= n) L_vec[i].push_back(FR[i]);
	}

	segment::build();
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		QL[l].push_back({i, r});
	}

	for (int l = n; l > 0; l--) {
		for (int mid : L_vec[l]) {
			int val = A[l] + A[mid];
			int r = mid + mid - l;
			if (r <= n) segment::update(r, n, val);
		}

		for (auto [q, r] : QL[l])
			ans[q] = segment::query(l + 2, r);
	}

	for (int i = 1; i <= q; i++)
		cout << ans[i] << endl;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23872 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23768 KB Output is correct
8 Correct 13 ms 23852 KB Output is correct
9 Correct 12 ms 23752 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23872 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23768 KB Output is correct
8 Correct 13 ms 23852 KB Output is correct
9 Correct 12 ms 23752 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 223 ms 46904 KB Output is correct
12 Correct 333 ms 46860 KB Output is correct
13 Correct 237 ms 46924 KB Output is correct
14 Correct 222 ms 46972 KB Output is correct
15 Correct 223 ms 46924 KB Output is correct
16 Correct 231 ms 46412 KB Output is correct
17 Correct 310 ms 46420 KB Output is correct
18 Correct 244 ms 46120 KB Output is correct
19 Correct 256 ms 46924 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 854 ms 52428 KB Output is correct
2 Execution timed out 4050 ms 40640 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23872 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23768 KB Output is correct
8 Correct 13 ms 23852 KB Output is correct
9 Correct 12 ms 23752 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 223 ms 46904 KB Output is correct
12 Correct 333 ms 46860 KB Output is correct
13 Correct 237 ms 46924 KB Output is correct
14 Correct 222 ms 46972 KB Output is correct
15 Correct 223 ms 46924 KB Output is correct
16 Correct 231 ms 46412 KB Output is correct
17 Correct 310 ms 46420 KB Output is correct
18 Correct 244 ms 46120 KB Output is correct
19 Correct 256 ms 46924 KB Output is correct
20 Correct 854 ms 52428 KB Output is correct
21 Execution timed out 4050 ms 40640 KB Time limit exceeded
22 Halted 0 ms 0 KB -