oj.uz

답안 #797149

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797149 2023-07-29T07:20:33 Z Sohsoh84 3단 점프 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -