oj.uz

답안 #1116235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1116235 2024-11-21T11:19:52 Z sinatbtfard 3단 점프 (JOI19_jumps) C++17
0 / 100
 211 ms 70312 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = 21, kaf = 1 << 20, inf = 1e15;

struct segment {
	int seg[1 << maxn], mx[1 << maxn], lazy[1 << maxn];
	segment (){
		for (int i = 0; i < (1 << maxn); i++)
			seg[i] = lazy[i] = 0;
	}
	void build (int i){
		if ((i << 1) >= (1 << maxn)) return;
		build(i << 1), build((i << 1) ^ 1);
		mx[i] = max(mx[i << 1], mx[(i << 1) ^ 1]);
	}
	void shift (int i){
		if ((i << 1) >= (1 << maxn)) return;
		lazy[i << 1] = max(lazy[i << 1], lazy[i]);
		lazy[(i << 1) ^ 1] = max(lazy[(i << 1) ^ 1], lazy[i]);
		seg[i << 1] = max(seg[i << 1], mx[i << 1] + lazy[i << 1]);
		seg[(i << 1) ^ 1] = max(seg[(i << 1) ^ 1], mx[(i << 1) ^ 1] + lazy[(i << 1) ^ 1]);
		lazy[i] = 0;
	}
	void update (int i, int L, int R, int l, int r, int x){
		if (L > r || R < l) return;
		if (L >= l && R <= r){
			lazy[i] = max(lazy[i], x);
			seg[i] = max(seg[i], mx[i] + lazy[i]);
			return;
		}
		shift(i);
		int mid = (R + L) >> 1;
		update(i << 1, L, mid, l, r, x);
		update((i << 1) ^ 1, mid + 1, R, l, r, x);
		seg[i] = max(seg[i << 1], seg[(i << 1) ^ 1]);
	}
	int get (int i, int L, int R, int l, int r){
		if (L > r || R < l) return 0;
		if (L >= l && R <= r) return seg[i];
		shift(i);
		int mid = (R + L) >> 1;
		return max(get(i << 1, L, mid, l, r), get((i << 1) ^ 1, mid + 1, R, l, r));
	}
};

segment seg;

int n, q;

int32_t main (){
	ios_base::sync_with_stdio(0);
	cin >> n;
	vector <int> a(n), p[2 * n];
	vector <pair <int, int>> que[n];
	for (int i = 0; i < n; i++)
		cin >> a[i], seg.mx[kaf + i] = a[i];
	seg.build(1);
	cin >> q;
	vector <int> ans(q);
	for (int l, r, i = 0; i < q; i++)
		cin >> l >> r,
		que[--l].push_back({--r, i});
	stack <int> stc;
	for (int i = 0; i < n; i++){
		while (stc.size() && a[i] < a[stc.top()])
			p[stc.top()].push_back(i),
			stc.pop();
		if (stc.size()) p[stc.top()].push_back(i);
		stc.push(i);
	}
	for (int i = n - 1; ~i; i--){
		for (auto r : p[i])
			if (2 * r - i < n)
				seg.update(1, 0, kaf - 1, 2 * r - i, n - 1, a[i] + a[r]);
		for (auto [r, ind] : que[i])
			ans[ind] = seg.get(1, 0, kaf - 1, i, r);
	}
	for (int i : ans) cout << i << '\n';
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 43344 KB Output is correct
2 Incorrect 11 ms 43344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 43344 KB Output is correct
2 Incorrect 11 ms 43344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 211 ms 70312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 43344 KB Output is correct
2 Incorrect 11 ms 43344 KB Output isn't correct
3 Halted 0 ms 0 KB -