Submission #138410

#	Time	Username	Problem	Language	Result	Execution time	Memory
138410		qkxwsm	Triple Jump (JOI19_jumps)	C++14	100 / 100	2069 ms	234656 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define MAXN 5300013
#define MAGIC 811

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef array<array<int, 3>, 3> dparr;

int N, Q;
int arr[MAXN];
int sparse[20][MAXN];
vpi pos;
vpi quer[MAXN];
int ans[MAXN];
dparr seg[MAXN << 1];

dparr comb(dparr l, dparr r)
{
	dparr res;
	FOR(i, 0, 3)
	{
		FOR(j, i, 3)
		{
			res[i][j] = -INF;
			FOR(k, i, j + 1)
			{
				ckmax(res[i][j], l[i][k] + r[k][j]);
			}
		}
	}
	return res;
}
void build(int w, int L, int R)
{
	if (L == R)
	{
		FOR(i, 0, 3)
		{
			FOR(j, 0, 3)
			{
				seg[w][i][j] = -INF;
			}
			seg[w][i][i] = 0;
		}
		seg[w][1][2] = arr[L];
		return;
	}
	int mid = (L + R) >> 1;
	build(w << 1, L, mid);
	build(w << 1 | 1, mid + 1, R);
	seg[w] = comb(seg[w << 1], seg[w << 1 | 1]);
	return;
}
void update(int w, int L, int R, int a, int v)
{
	if (L == R)
	{
		ckmax(seg[w][0][1], v);
		seg[w][0][2] = seg[w][0][1] + seg[w][1][2];
		return;
	}
	int mid = (L + R) >> 1;
	if (a <= mid) update(w << 1, L, mid, a, v);
	else update(w << 1 | 1, mid + 1, R, a, v);
	seg[w] = comb(seg[w << 1], seg[w << 1 | 1]);
	// cerr << L << ' ' << R << ":\n";
	// FOR(i, 0, 3)
	// {
	// 	FOR(j, 0, 3)
	// 	{
	// 		cerr << seg[w][i][j] << ' ';
	// 	}
	// 	cerr << endl;
	// }
}
dparr query(int w, int L, int R, int a, int b)
{
	if (a <= L && R <= b)
	{
		return seg[w];
	}
	int mid = (L + R) >> 1;
	if (b <= mid) return query(w << 1, L, mid, a, b);
	if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
	return comb(query(w << 1, L, mid, a, b), query(w << 1 | 1, mid + 1, R, a, b));
}
int qry(int l, int r)
{
	//max F[i] + A[j] for for l <= i <= j <= x
	// cerr << "QUERY " << l << ' ' << r << endl;
	dparr res = query(1, 0, N - 1, l, r);
	return res[0][2];
}
void proc(int l, int m)
{
	int r = 2 * m - l;
	if (r >= N) return;
	// cerr << "UPDATE " << r << ' ' << arr[l] + arr[m] << endl;
	update(1, 0, N - 1, r, arr[l] + arr[m]);
	// cerr << "PROC " << l << ' ' << m << endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	FOR(i, 0, N) cin >> arr[i];
	cin >> Q;
	FOR(i, 0, N)
	{
		sparse[0][i] = arr[i];
	}
	FOR(i, 0, 20)
	{
		FOR(j, 0, N)
		{
			if (j + (1 << i) < N)
			{
				sparse[i + 1][j] = max(sparse[i][j], sparse[i][j + (1 << i)]);
			}
		}
	}
	FOR(i, 0, Q)
	{
		int l, r; cin >> l >> r; l--; r--;
		quer[l].PB({r, i});
	}
	build(1, 0, N - 1);
	//everything in between (l..r) must be less than a[l] and a[r]
	//find all (l..r) such that everything between them is <= them
	FORD(i, N, 0)
	{
		int x = arr[i];
		while(!pos.empty() && pos.back().fi <= arr[i])
		{
			proc(i, pos.back().se);
			pos.pop_back();
		}
		if (!pos.empty())
		{
			proc(i, pos.back().se);
		}
		pos.PB({x, i});
		for (pii p : quer[i])
		{
			ans[p.se] = qry(i, p.fi);
		}
	}
	FOR(i, 0, Q)
	{
		cout << ans[i] << '\n';
	}
	return 0;
}

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