Submission #202507

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
202507	2020-02-16T15:55:54 Z	cookiedoth	Triple Jump (JOI19_jumps)	C++14	100 / 100	3018 ms	166560 KB

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 + 2e4;
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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	236 ms	14712 KB	Output is correct
12	Correct	235 ms	14584 KB	Output is correct
13	Correct	210 ms	14712 KB	Output is correct
14	Correct	236 ms	14712 KB	Output is correct
15	Correct	235 ms	14712 KB	Output is correct
16	Correct	232 ms	14072 KB	Output is correct
17	Correct	228 ms	13948 KB	Output is correct
18	Correct	228 ms	14072 KB	Output is correct
19	Correct	234 ms	14584 KB	Output is correct

Subtask #3

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	830 ms	58616 KB	Output is correct
2	Correct	459 ms	52344 KB	Output is correct
3	Correct	336 ms	52312 KB	Output is correct
4	Correct	826 ms	58616 KB	Output is correct
5	Correct	809 ms	58616 KB	Output is correct
6	Correct	806 ms	58616 KB	Output is correct
7	Correct	838 ms	58616 KB	Output is correct
8	Correct	823 ms	58616 KB	Output is correct
9	Correct	810 ms	58616 KB	Output is correct

Subtask #4

54.0 / 54.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	236 ms	14712 KB	Output is correct
12	Correct	235 ms	14584 KB	Output is correct
13	Correct	210 ms	14712 KB	Output is correct
14	Correct	236 ms	14712 KB	Output is correct
15	Correct	235 ms	14712 KB	Output is correct
16	Correct	232 ms	14072 KB	Output is correct
17	Correct	228 ms	13948 KB	Output is correct
18	Correct	228 ms	14072 KB	Output is correct
19	Correct	234 ms	14584 KB	Output is correct
20	Correct	830 ms	58616 KB	Output is correct
21	Correct	459 ms	52344 KB	Output is correct
22	Correct	336 ms	52312 KB	Output is correct
23	Correct	826 ms	58616 KB	Output is correct
24	Correct	809 ms	58616 KB	Output is correct
25	Correct	806 ms	58616 KB	Output is correct
26	Correct	838 ms	58616 KB	Output is correct
27	Correct	823 ms	58616 KB	Output is correct
28	Correct	810 ms	58616 KB	Output is correct
29	Correct	2902 ms	160492 KB	Output is correct
30	Correct	1931 ms	144872 KB	Output is correct
31	Correct	1540 ms	144772 KB	Output is correct
32	Correct	2929 ms	160504 KB	Output is correct
33	Correct	3018 ms	160504 KB	Output is correct
34	Correct	2950 ms	159840 KB	Output is correct
35	Correct	2817 ms	159776 KB	Output is correct
36	Correct	2785 ms	159712 KB	Output is correct
37	Correct	2961 ms	160376 KB	Output is correct
38	Correct	2503 ms	166288 KB	Output is correct
39	Correct	2453 ms	166560 KB	Output is correct
40	Correct	2429 ms	164388 KB	Output is correct
41	Correct	2450 ms	164344 KB	Output is correct
42	Correct	2484 ms	164344 KB	Output is correct
43	Correct	2425 ms	165112 KB	Output is correct
44	Correct	2510 ms	165648 KB	Output is correct
45	Correct	2494 ms	165764 KB	Output is correct
46	Correct	2494 ms	164012 KB	Output is correct
47	Correct	2425 ms	164108 KB	Output is correct
48	Correct	2400 ms	163988 KB	Output is correct
49	Correct	2443 ms	165380 KB	Output is correct
50	Correct	2546 ms	163668 KB	Output is correct
51	Correct	2573 ms	163628 KB	Output is correct
52	Correct	2551 ms	162652 KB	Output is correct
53	Correct	2548 ms	162684 KB	Output is correct
54	Correct	2534 ms	162588 KB	Output is correct
55	Correct	2512 ms	163256 KB	Output is correct