Submission #202506

#	Time	Username	Problem	Language	Result	Execution time	Memory
202506		cookiedoth	Triple Jump (JOI19_jumps)	C++14	46 / 100	832 ms	118392 KiB

jumps

/*

Code for problem D by cookiedoth
Generated 16 Feb 2020 at 02.47 P


──────▄▌▐▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▌
───▄▄██▌█░ВЕЗЁМ▄▀▀▀▄░ГУСЕЙ░░░░░░░
───████▌█▄███▀░◐░▄▀▀▀▄░░РАБОТЯГИ░
──██░░█▌█░░▄███▀░◐░░▄▀▀▀▄░░░░░░░
─██░░░█▌█░░░░▐░▄▀▀▀▌░░░░◐░▀███▄░
▄██████▌█▄███▀░◐░░░▌░░░░░▐░░░░░░
███████▌█░░░░▌░░░░░▌░░░░░▐░░░░░░
███████▌█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▌
▀(@)▀▀▀▀▀▀▀(@)(@)▀▀▀▀▀▀▀▀▀▀▀▀▀(@)▀(@)

-_-
z_z
=_=

*/

#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 rall(a) a.rbegin(), a.rend()
#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);
}

/** Fast input-output */

template <class T = int> inline T readInt();						
inline double readDouble();
inline int readUInt();					 
inline int readChar(); // first non-blank character
inline void readWord(char *s); 
inline bool readLine(char *s); // do not save '\n'
inline bool isEof();
inline int getChar(); 
inline int peekChar();
inline bool seekEof();
inline void skipBlanks();

template <class T> inline void writeInt(T x, char end = 0, int len = -1);
inline void writeChar(int x); 
inline void writeWord(const char *s);
inline void writeDouble(double x, int len = 0);
inline void flush();

static struct buffer_flusher_t {
	~buffer_flusher_t() {
		flush();
	}
} buffer_flusher;

/** Read */

static const int buf_size = 4096;

static unsigned char buf[buf_size];
static int buf_len = 0, buf_pos = 0;

inline bool isEof() {
	if (buf_pos == buf_len) {
		buf_pos = 0, buf_len = fread(buf, 1, buf_size, stdin);
		if (buf_pos == buf_len)
			return 1;
	}
	return 0;
}

inline int getChar() { 
	return isEof() ? -1 : buf[buf_pos++];
}

inline int peekChar() { 
	return isEof() ? -1 : buf[buf_pos];
}

inline bool seekEof() { 
	int c;
	while ((c = peekChar()) != -1 && c <= 32)
		buf_pos++;
	return c == -1;
}

inline void skipBlanks() {
	while (!isEof() && buf[buf_pos] <= 32U)
		buf_pos++;
}

inline int readChar() {
	int c = getChar();
	while (c != -1 && c <= 32)
		c = getChar();
	return c;
}

inline int readUInt() {
	int c = readChar(), x = 0;
	while ('0' <= c && c <= '9')
		x = x * 10 + c - '0', c = getChar();
	return x;
}

template <class T>
inline T readInt() {
	int s = 1, c = readChar();
	T x = 0;
	if (c == '-')
		s = -1, c = getChar();
	else if (c == '+')
		c = getChar();
	while ('0' <= c && c <= '9')
		x = x * 10 + c - '0', c = getChar();
	return s == 1 ? x : -x;
}

inline double readDouble() {
	int s = 1, c = readChar();
	double x = 0;
	if (c == '-')
		s = -1, c = getChar();
	while ('0' <= c && c <= '9')
		x = x * 10 + c - '0', c = getChar();
	if (c == '.') {
		c = getChar();
		double coef = 1;
		while ('0' <= c && c <= '9')
			x += (c - '0') * (coef *= 1e-1), c = getChar();
	}
	return s == 1 ? x : -x;
}

inline void readWord(char *s) { 
	int c = readChar();
	while (c > 32)
		*s++ = c, c = getChar();
	*s = 0;
}

inline bool readLine(char *s) { 
	int c = getChar();
	while (c != '\n' && c != -1)
		*s++ = c, c = getChar();
	*s = 0;
	return c != -1;
}

/** Write */

static int write_buf_pos = 0;
static char write_buf[buf_size];

inline void writeChar(int x) {
	if (write_buf_pos == buf_size)
		fwrite(write_buf, 1, buf_size, stdout), write_buf_pos = 0;
	write_buf[write_buf_pos++] = x;
}

inline void flush() {
	if (write_buf_pos) {
		fwrite(write_buf, 1, write_buf_pos, stdout), write_buf_pos = 0;
		fflush(stdout);
	}
}

template <class T> 
inline void writeInt(T x, char end, int output_len) {
	if (x < 0)
		writeChar('-'), x = -x;

	char s[24];
	int n = 0;
	while (x || !n)
		s[n++] = '0' + x % 10, x /= 10;
	while (n < output_len)
		s[n++] = '0';
	while (n--)
		writeChar(s[n]);
	if (end)
		writeChar(end);
}

inline void writeWord(const char *s) {
	while (*s)
		writeChar(*s++);
}

inline void writeDouble(double x, int output_len) {
	if (x < 0)
		writeChar('-'), x = -x;
	int t = (int)x;
	writeInt(t), x -= t;
	writeChar('.');
	for (int i = output_len - 1; i > 0; i--) {
		x *= 10;
		t = std::min(9, (int)x);
		writeChar('0' + t), x -= t;
	}
	x *= 10;
	t = std::min(9, (int)(x + 0.5));
	writeChar('0' + t);
}

const int INF = 1e9;


struct rmq {
	vector<int> t;
	int n;

	rmq() {}

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

	void build(int *a, int _n) {
		n = 1;
		while (n < _n) {
			n <<= 1;
		}
		t.resize(2 * n);
		build(a, 1, 0, n - 1);
	}

	void init(int _n) {
		n = 1;
		while (n < _n) {
			n <<= 1;
		}
		t.resize(2 * n);
	}

	int get(int l, int r) {
		l += n;
		r += n;
		int res = 0;
		while (l <= r) {
			if (l & 1) {
				chkmax(res, t[l]);
				l++;
			}
			if ((r & 1) == 0) {
				chkmax(res, t[r]);
				r--;
			}
			l >>= 1;
			r >>= 1;
		}
		return res;
	}

	void update(int pos, int val) {
		int v = pos + n;
		t[v] = val;
		while (v > 1) {
			v >>= 1;
			t[v] = max(t[v * 2], t[v * 2 + 1]);
		}
	}
};

ll C = 0;

struct stb {
	vector<int> min_val1, min_val2, max_res1, max_res2, mod;
	int n;

	stb() {}

	void init(int _n) {
		n = _n;
		// cerr << "init " << _n << endl;
		min_val1.resize(4 * n, -INF);
		min_val2.resize(4 * n, -INF);
		max_res1.resize(4 * n, -2 * INF);
		max_res2.resize(4 * n, -2 * INF);
		mod.resize(4 * n, 0);
	}

	void push(int v) {
		if (min_val1[v * 2] + mod[v * 2] == min_val1[v]) {
			mod[v * 2] += mod[v];
		}
		if (min_val1[v * 2 + 1] + mod[v * 2 + 1] == min_val1[v]) {
			mod[v * 2 + 1] += mod[v];
		}
		max_res1[v] += mod[v];
		if (min_val1[v] == min_val2[v]) {
			min_val2[v] += mod[v];
		}
		min_val1[v] += mod[v];
		mod[v] = 0;
	}

	void merge(int v, int v1) {
		// cerr << "merge " << v << " " << v1 << " " << min_val1[v1] << " " << min_val2[v1] << " " << max_res1[v1] << " " << max_res2[v1] << endl;
		if (min_val1[v1] + mod[v1] == min_val1[v]) {
			chkmax(max_res1[v], max_res1[v1] + mod[v1]);
		} else {
			chkmin(min_val2[v], min_val1[v1] + mod[v1]);
			chkmax(max_res2[v], max_res1[v1] + mod[v1]);
		}
		if (min_val2[v1] != min_val1[v1]) {
			chkmin(min_val2[v], min_val2[v1]);
			chkmax(max_res2[v], max_res2[v1]);
		}
	}

	void recalc(int v) {
		// cerr << "uhuhuhu " << v << " " << max_res1[v * 2] << " " << max_res2[v * 2] << " " << max_res1[v * 2 + 1] << " " << max_res2[v * 2 + 1] << endl;
		// cerr << "mododod " << mod[v * 2] << " " << mod[v * 2 + 1] << endl;
		min_val1[v] = min(min_val1[v * 2] + mod[v * 2], min_val1[v * 2 + 1] + mod[v * 2 + 1]);
		min_val2[v] = INF;
		max_res1[v] = -2 * INF;
		max_res2[v] = -2 * INF;
		merge(v, 2 * v);
		merge(v, v * 2 + 1);
		if (min_val2[v] == INF) {
			min_val2[v] = min_val1[v];
		}
		// cerr << "recalced " << v << endl;
		// cerr << min_val1[v] << " " << min_val2[v] << " " << max_res1[v] << " " << max_res2[v] << endl;
	}

	void update(int val, int v, int tl, int tr) {
		C++;
		if (min_val1[v] == min_val2[v] || val < min_val2[v]) {
			if (val > min_val1[v] + mod[v]) {
				mod[v] = val - min_val1[v];
			}
			// cerr << "mod " << v << " = " << mod[v] << endl;
			return;
		} else {
			int tm = (tl + tr) >> 1;
			push(v);
			update(val, v * 2, tl, tm);
			update(val, v * 2 + 1, tm + 1, tr);
			recalc(v);
		}
	}

	void chkmax_val(int val) {
		// cerr << "QUERY: chkmax_val " << val << endl;
		update(val, 1, 0, n - 1);
	}

	void update_val(int pos, int val, int v, int tl, int tr) {
		if (tl == tr) {
			int delta = (val - min_val1[v] - mod[v]);
			min_val1[v] = min_val2[v] = val;
			max_res1[v] += (mod[v] + delta);
			max_res2[v] = -2 * INF;
			mod[v] = 0;
		} else {
			int tm = (tl + tr) >> 1;
			push(v);
			if (pos <= tm) {
				update_val(pos, val, v * 2, tl, tm);
			} else {
				update_val(pos, val, v * 2 + 1, tm + 1, tr);
			}
			recalc(v);
		}
	}

	void change_val(int pos, int val) {
		// cerr << "QUERY: change_val " << pos << " " << val << endl;
		update_val(pos, val, 1, 0, n - 1);
	}

	void update_sum(int pos, int val, int v, int tl, int tr) {
		if (tl == tr) {
			max_res1[v] = val + min_val1[v];
			// cerr << "max_res1 " << v << " = " << max_res1[v] << endl;
		} else {
			int tm = (tl + tr) >> 1;
			push(v);
			if (pos <= tm) {
				update_sum(pos, val, v * 2, tl, tm);
			} else {
				update_sum(pos, val, v * 2 + 1, tm + 1, tr);
			}
			recalc(v);
		}
	}

	void change_sum(int pos, int val) {
		// cerr << "QUERY: change_sum " << pos << " " << val << endl;
		update_sum(pos, val, 1, 0, n - 1);
	}

	int get(int l, int r, int v, int tl, int tr) {
		if (r < tl || l > tr) {
			return -2 * INF;
		}
		if (l <= tl && tr <= r) {
			return max(max_res1[v] + mod[v], max_res2[v]);
		}
		int tm = (tl + tr) >> 1;
		push(v);
		int res_l = get(l, r, v * 2, tl, tm);
		int res_r = get(l, r, v * 2 + 1, tm + 1, tr);
		return max(res_l, res_r);
	}

	int get(int l, int r) {
		int res = get(l, r, 1, 0, n - 1);
		// cerr << "QUERY: get " << l << " " << r << " = " << res << endl;
		return res;
	}
};

const int mx = 5e5 + 1e4;
int n, arr[mx], m, ans[mx];
vector<vector<pair<int, int> > > lq, rseg, sum_update, val_update;
rmq arr_rmq, q_rmq;
stb T;

void read() {
	n = readInt();
	if (n > 500000) {
		exit(0);
	}
	for (int i = 0; i < n; ++i) {
		arr[i] = readInt();
	}
	lq.resize(n);
	m = readInt();
	if (m > 500000) {
		exit(0);
	}
	for (int i = 0; i < m; ++i) {
		int l, r;
		l = readInt();
		r = readInt();
		l--;
		r--;
		lq[r].emplace_back(l, i);
	}
}

void add(int a, int b) {
	// cerr << "add " << a << " " << b << endl;
	int c = b + (b - a);
	int sum = arr[a] + arr[b];
	if (c < n) {
		rseg[a].emplace_back(c, sum);
	}
}

void gen_rseg() {
	rseg.resize(n);
	vector<int> st;
	for (int i = 0; i < n; ++i) {
		while (!st.empty() && arr[i] >= arr[st.back()]) {
			add(st.back(), i);
			st.pop_back();
		}
		if (!st.empty()) {
			add(st.back(), i);
		}
		st.push_back(i);
	}
}

void make_rseg() {
	vector<pair<int, int> > new_rseg;
	for (int a = 0; a < n; ++a) {
		new_rseg.clear();
		int last_sum = 0;
		sort(all(rseg[a]));
		for (auto pp : rseg[a]) {
			if (pp.second > last_sum) {
				new_rseg.push_back(pp);
				last_sum = pp.second;
			}
		}
		rseg[a] = new_rseg;
		// cerr << "new_rseg " << a << endl;
		// for (auto pp : rseg[a]) {
		// 	cerr << pp.first << " " << pp.second << endl;
		// }
	}
}

void get_updates() {
	arr_rmq.build(arr, n);
	sum_update.resize(n);
	val_update.resize(n);
	for (int a = 0; a < n; ++a) {
		int last_val = 0;
		for (int i = 0; i < (int)rseg[a].size(); ++i) {
			auto pp = rseg[a][i];
			sum_update[pp.first].emplace_back(a, pp.second);
			if (i) {
				int new_val = rseg[a][i - 1].second + arr_rmq.get(rseg[a][i - 1].first, pp.first - 1);
				if (chkmax(last_val, new_val)) {
					val_update[pp.first].emplace_back(a, new_val);
				}
			}
		}
	}
}

void super_scanline() {
	q_rmq.init(n);
	T.init(n);
	for (int i = 0; i < n; ++i) {
		for (auto pp : val_update[i]) {
			q_rmq.update(pp.first, pp.second);
		}
		for (auto pp : sum_update[i]) {
			T.change_val(pp.first, 0);
			T.change_sum(pp.first, pp.second);
		}
		T.chkmax_val(arr[i]);
		for (auto pp : lq[i]) {
			// cerr << "get " << pp.second << endl;
			int res1 = q_rmq.get(pp.first, n - 1);
			int res2 = T.get(pp.first, n - 1);
			ans[pp.second] = max(res1, res2);
		}
	}
}

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

signed main() {
	fast_io();
	read();
	gen_rseg();
	make_rseg();
	get_updates();
	super_scanline();
	print_ans();
}

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