oj.uz

Submission #797152

# Submission time Handle Problem Language Result Execution time Memory
797152 2023-07-29T07:21:53 Z Sohsoh84 Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 52408 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 || val <= tof[v]) 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 12 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23880 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 15 ms 23880 KB Output is correct
6 Correct 13 ms 23752 KB Output is correct
7 Correct 12 ms 23780 KB Output is correct
8 Correct 12 ms 23836 KB Output is correct
9 Correct 13 ms 23764 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 12 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23880 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 15 ms 23880 KB Output is correct
6 Correct 13 ms 23752 KB Output is correct
7 Correct 12 ms 23780 KB Output is correct
8 Correct 12 ms 23836 KB Output is correct
9 Correct 13 ms 23764 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 268 ms 46964 KB Output is correct
12 Correct 367 ms 46792 KB Output is correct
13 Correct 239 ms 46880 KB Output is correct
14 Correct 258 ms 46956 KB Output is correct
15 Correct 285 ms 47020 KB Output is correct
16 Correct 286 ms 46464 KB Output is correct
17 Correct 244 ms 46328 KB Output is correct
18 Correct 263 ms 46232 KB Output is correct
19 Correct 269 ms 46932 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 52408 KB Output is correct
2 Execution timed out 4066 ms 40824 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23880 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 15 ms 23880 KB Output is correct
6 Correct 13 ms 23752 KB Output is correct
7 Correct 12 ms 23780 KB Output is correct
8 Correct 12 ms 23836 KB Output is correct
9 Correct 13 ms 23764 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 268 ms 46964 KB Output is correct
12 Correct 367 ms 46792 KB Output is correct
13 Correct 239 ms 46880 KB Output is correct
14 Correct 258 ms 46956 KB Output is correct
15 Correct 285 ms 47020 KB Output is correct
16 Correct 286 ms 46464 KB Output is correct
17 Correct 244 ms 46328 KB Output is correct
18 Correct 263 ms 46232 KB Output is correct
19 Correct 269 ms 46932 KB Output is correct
20 Correct 716 ms 52408 KB Output is correct
21 Execution timed out 4066 ms 40824 KB Time limit exceeded
22 Halted 0 ms 0 KB -