Submission #797156

#	Time	Username	Problem	Language	Result	Execution time	Memory
797156		Sohsoh84	Triple Jump (JOI19_jumps)	C++17	0 / 100	54 ms	40196 KiB

jumps

#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], mn_tof[MAXN << 2], mx_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]) {
			mn_tof[v] += lz[v] - tof[v];
			mx_tof[v] += 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 <= mx_tof[v]) return;
		if (ql <= l && qr >= r && val >= mn_tof[v]) {
			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]);	
		mn_tof[v] = min(mn_tof[v << 1], mn_tof[v << 1 | 1]);
		mx_tof[v] = max(mx_tof[v << 1], mx_tof[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: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54