Submission #853702

#	Time	Username	Problem	Language	Result	Execution time	Memory
853702		LeonaRaging	Triple Jump (JOI19_jumps)	C++14	0 / 100	178 ms	57112 KiB

jumps

#include<bits/stdc++.h>
using namespace std;

#define pb emplace_back

const int maxn = 5e5 + 3;
const int INF = 1e9;

void MAX(int &a, int b) {
	if (a < b) a = b;
}

int a[maxn];

struct seg_tree {
	vector<int> t, t2, lazy;
	seg_tree() {
		t.resize(4 * maxn);
		t2.resize(4 * maxn);
		lazy.resize(4 * maxn);
	}
	void pushdown(int v) {
		int val = lazy[v];
		MAX(t[2 * v], val);
		MAX(t[2 * v + 1], val);
		MAX(lazy[2 * v], val);
		MAX(lazy[2 * v + 1], val);
	}
	void build(int v = 1, int l = 1, int r = maxn - 1) {
		if (l == r) {
			t2[v] = a[l];
			return;
		}
		int m = (l + r) / 2;
		build(2 * v, l, m);
		build(2 * v + 1, m + 1, r);
		t2[v] = max(t2[2 * v], t2[2 * v + 1]);
	}
	void update(int l, int r, int val, int v = 1, int tl = 1, int tr = maxn - 1) {
		if (tl > r || tr < l) return;
		if (tl >= l && tr <= r) {
			MAX(t[v], val);
			MAX(lazy[v], val);
			return;
		}
		pushdown(v);
		int m = (tl + tr) / 2;
		update(l, r, val, 2 * v, tl, m);
		update(l, r, val, 2 * v + 1, m + 1, tr);
		t[v] = max(t[2 * v], t[2 * v + 1]);
	}
	int get(int l, int r, int v = 1, int tl = 1, int tr = maxn - 1) {
		if (tl > r || tr < l) return 0;
		if (tl >= l && tr <= r) return t[v] + t2[v];
		pushdown(v);
		int m = (tl + tr) / 2;
		return max(get(l, r, 2 * v, tl, m), get(l, r, 2 * v + 1, m + 1, tr));
	}
} IT;

int n, q, R[maxn], res[maxn];
vector<pair<int,int>> que[maxn];
stack<int> st;
vector<int> L[maxn];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	if (fopen("TRIPLE.INP", "r")) {
		freopen("TRIPLE.INP", "r", stdin);
		freopen("TRIPLE.OUT", "w", stdout);
	}
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	IT.build();
	st.push(0); a[0] = INF;
	for (int i = 1; i <= n; i++) {
		while (a[i] > a[st.top()])
			st.pop();
		L[st.top()].pb(i);
		st.push(i);
	}
	cin >> q;
	for (int i = 1, l, r; i <= q; i++) {
		cin >> l >> r;
		que[l].pb(r, i);
	}
	stack<int>().swap(st);
	st.push(n + 1); a[n + 1] = INF;
	for (int i = n; i >= 1; i--) {
		while (a[i] > a[st.top()])
			st.pop();
		R[i] = st.top();
		IT.update(2 * R[i] - i, n, a[i] + a[R[i]]);
		for (int j : L[i])
			IT.update(2 * j - i, n, a[i] + a[j]);
		st.push(i);
		for (auto it : que[i])
			res[it.second] = IT.get(i, it.first);
	}
	for (int i = 1; i <= q; i++)
		cout << res[i] << '\n';
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:71:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   freopen("TRIPLE.INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:72:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   freopen("TRIPLE.OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54