Submission #757114

#	Time	Username	Problem	Language	Result	Execution time	Memory
757114		jmyszka2007	3단 점프 (JOI19_jumps)	C++17	100 / 100	1750 ms	91468 KiB

jumps

#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);
	lasy[2 * v] = max(lasy[2 * v], lasy[v]);
	lasy[2 * v + 1] = max(lasy[2 * v + 1], lasy[v]);
}
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: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54