Submission #142534

#	Time	Username	Problem	Language	Result	Execution time	Memory
142534		cookiedoth	Triple Jump (JOI19_jumps)	C++14	100 / 100	1359 ms	101692 KiB

jumps

/*

Code for problem A by cookiedoth
Generated 09 Aug 2019 at 01.49 P


   ,##.                   ,==.
 ,#    #.                 \ o ',
#        #     _     _     \    \
#        #    (_)   (_)    /    ; 
 `#    #'                 /   .'  
   `##'                   "=="

¯\_(ツ)_/¯
o_O
-_-

*/

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define sz(a) (int)a.size()

using namespace std;

template<class T> int chkmax(T &a, T b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmin(T &a, T b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(T x, ostream& out = cerr) {
	output(x.begin(), x.end(), out);
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const int INF = 1e9;

struct node {
	int value, max_arr, max_sum;

	node(): value(-INF), max_arr(0), max_sum(-INF) {}
	node(int _value, int _max_arr, int _max_sum): value(_value), max_arr(_max_arr), max_sum(_max_sum) {}
};

node operator + (node a, node b) {
	return node(-INF, max(a.max_arr, b.max_arr), max(a.max_sum, b.max_sum));
}

void update(node &a) {
	chkmax(a.max_sum, a.value + a.max_arr);
}

struct st {
	vector<node> t;
	int n;

	st() {}

	void build(int *arr, int v, int tl, int tr) {
		if (tl == tr) {
			t[v].max_arr = arr[tl];
		}
		else {
			int tm = (tl + tr) >> 1;
			build(arr, v * 2, tl, tm);
			build(arr, v * 2 + 1, tm + 1, tr);
			t[v].max_arr = max(t[v * 2].max_arr, t[v * 2 + 1].max_arr);
		}
	}

	void build(int *arr, int _n) {
		n = _n;
		t.resize(4 * n);
		build(arr, 1, 0, n - 1);
	}

	void push(int v) {
		chkmax(t[v * 2].value, t[v].value);
		chkmax(t[v * 2 + 1].value, t[v].value);
		::update(t[v * 2]);
		::update(t[v * 2 + 1]);
		t[v].value = -INF;
	}

	void update(int l, int r, int value, int v, int tl, int tr) {
		if (l > r) {
			return;
		}
		if (l == tl && r == tr) {
			chkmax(t[v].value, value);
			::update(t[v]);
		}
		else {
			int tm = (tl + tr) >> 1;
			push(v);
			update(l, min(r, tm), value, v * 2, tl, tm);
			update(max(l, tm + 1), r, value, v * 2 + 1, tm + 1, tr);
			t[v] = t[v * 2] + t[v * 2 + 1];
		}
	}

	int get(int l, int r, int v, int tl, int tr) {
		if (l > r) {
			return -INF;
		}
		if (l == tl && r == tr) {
			return t[v].max_sum;
		}
		else {
			int tm = (tl + tr) >> 1;
			push(v);
			int res_l = get(l, min(r, tm), v * 2, tl, tm);
			int res_r = get(max(l, tm + 1), r, v * 2 + 1, tm + 1, tr);
			return max(res_l, res_r);
		}
	}

	void update(int l, int r, int val) {
		update(l, r, val, 1, 0, n - 1);
	}

	int get(int l, int r) {
		int res = get(l, r, 1, 0, n - 1);
		return res;
	}
};

const int mx = 5e5 + 228;
int n, q, arr[mx], ans[mx];
vector<vector<pair<int, int> > > c_data, queries;

void read_a() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}
	queries.resize(n);
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r;
		l--;
		r--;
		queries[l].emplace_back(r, i);
	}
}

void add_ab(int a, int b) {
	int c = b + (b - a);
	if (c < n) {
		c_data[a].emplace_back(c, arr[a] + arr[b]);
	}
}

void build_c_data() {
	c_data.resize(n);
	vector<int> st;
	for (int i = 0; i < n; ++i) {
		while (!st.empty()) {
			int pos = st.back();
			add_ab(pos, i);
			if (arr[pos] <= arr[i]) {
				st.pop_back();
			}
			else {
				break;
			}
		}
		st.push_back(i);
	}
}

//int value[mx];
st t;

void scanline() {
	t.build(arr, n);
	for (int i = n - 1; i >= 0; --i) {
		for (auto pp : c_data[i]) {
			t.update(pp.first, n - 1, pp.second);
		}
		for (auto pp : queries[i]) {
			ans[pp.second] = t.get(i, pp.first);
		}
	}
}

void print_ans() {
	for (int i = 0; i < q; ++i) {
		cout << ans[i] << '\n';
	}
}

signed main() {
	fast_io();
	read_a();
	build_c_data();
	scanline();
	print_ans();
}

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