oj.uz

답안 #757095

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
757095 2023-06-12T15:27:55 Z jmyszka2007 3단 점프 (JOI19_jumps) C++17
27 / 100
 396 ms 43556 KB 
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pi pair<int, int>
#define vi vector<int>
#define pb push_back
//max1 = A + B, max2 = C, max3 = A + B + C
struct node {
	int max1, max2, max3;
};
constexpr int base = (1 << 19);
constexpr int LIM = 5e5;
node INF;
node tri[2 * base];
int tab[LIM + 10];
vi can[LIM + 10];
vector<pi> zap[LIM + 10];
int ans[LIM + 10];
int lasy[2 * base];
node merge(node a, node b) {
	node res;
	res.max1 = max(a.max1, b.max1);
	res.max2 = max(a.max2, b.max2);
	res.max3 = max({a.max3, b.max3, a.max1 + b.max2});
	return res;
}
void spl(int v) {
	tri[2 * v].max1 = max(tri[2 * v].max1, lasy[v]);
	tri[2 * v].max3 = max(tri[2 * v].max3, lasy[v] + tri[2 * v].max2);
	tri[2 * v + 1].max1 = max(tri[2 * v + 1].max1, lasy[v]);
	tri[2 * v + 1].max3 = max(tri[2 * v + 1].max3, lasy[v] + tri[2 * v + 1].max2);
}
void upd(int v, int l, int r, int a, int b, int x) {
	if(l > b || r < a) {
		return;
	}
	if(a <= l && r <= b) {
		tri[v].max1 = max(tri[v].max1, x);
		tri[v].max3 = max(tri[v].max3, x + tri[v].max2);
		lasy[v] = max(lasy[v], x);
		return;
	}
	spl(v);
	int mid = (l + r) / 2;
	upd(2 * v, l, mid, a, b, x);
	upd(2 * v + 1, mid + 1, r, a, b, x);
	tri[v] = merge(tri[2 * v], tri[2 * v + 1]);
}
node res;
void query(int v, int l, int r, int a, int b) {
	if(l > b || r < a) {
		return;
	}
	if(a <= l && r <= b) {
		res = merge(res, tri[v]);
		return;
	}
	spl(v);
	int mid = (l + r) / 2;
	query(2 * v, l, mid, a, b);
	query(2 * v + 1, mid + 1, r, a, b);
	tri[v] = merge(tri[2 * v], tri[2 * v + 1]);
}
int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	INF.max1 = -1e9, INF.max2 = -1e9, INF.max3 = -1e9; 
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> tab[i];
		tri[i + base - 1] = INF;
		tri[i + base - 1].max2 = tab[i];
	}
	for(int i = base - 1; i >= 1; i--) {
		tri[i] = merge(tri[2 * i], tri[2 * i + 1]);
	}
	stack<int>s;
	for(int i = 1; i <= n; i++) {
		while(!s.empty() && tab[s.top()] <= tab[i]) {
			can[s.top()].pb(i);
			s.pop();
		}
		if(!s.empty()) {
			can[s.top()].pb(i);
		}
		s.push(i);
	}
	int t;
	cin >> t;
	for(int i = 1; i <= t; i++) {
		int l, r;
		cin >> l >> r;
		zap[l].pb({r, i});
	}
	for(int i = n; i >= 1; i--) {
		for(auto x : can[i]) {
			upd(1, 1, base, 2 * x - i, n, tab[i] + tab[x]);
		}
		for(auto x : zap[i]) {
			res = INF;
			query(1, 1, base, i, x.st);
			ans[x.nd] = res.max3;
		}
	}
	for(int i = 1; i <= t; i++) {
		cout << ans[i] << '\n';
	}
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 364 ms 42812 KB Output is correct
2 Correct 219 ms 42692 KB Output is correct
3 Correct 240 ms 43556 KB Output is correct
4 Correct 369 ms 42896 KB Output is correct
5 Correct 389 ms 42808 KB Output is correct
6 Correct 336 ms 42336 KB Output is correct
7 Correct 396 ms 42136 KB Output is correct
8 Correct 350 ms 42156 KB Output is correct
9 Correct 364 ms 42456 KB Output is correct

Subtask #4
0 / 54.0

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