oj.uz

Submission #138410

# Submission time Handle Problem Language Result Execution time Memory
138410 2019-07-29T21:20:26 Z qkxwsm Triple Jump (JOI19_jumps) C++14
100 / 100
 2069 ms 234656 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 124920 KB Output is correct
2 Correct 128 ms 124920 KB Output is correct
3 Correct 128 ms 124884 KB Output is correct
4 Correct 138 ms 124920 KB Output is correct
5 Correct 190 ms 124920 KB Output is correct
6 Correct 138 ms 124920 KB Output is correct
7 Correct 123 ms 124844 KB Output is correct
8 Correct 138 ms 124920 KB Output is correct
9 Correct 118 ms 124920 KB Output is correct
10 Correct 118 ms 124920 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 124920 KB Output is correct
2 Correct 128 ms 124920 KB Output is correct
3 Correct 128 ms 124884 KB Output is correct
4 Correct 138 ms 124920 KB Output is correct
5 Correct 190 ms 124920 KB Output is correct
6 Correct 138 ms 124920 KB Output is correct
7 Correct 123 ms 124844 KB Output is correct
8 Correct 138 ms 124920 KB Output is correct
9 Correct 118 ms 124920 KB Output is correct
10 Correct 118 ms 124920 KB Output is correct
11 Correct 557 ms 143864 KB Output is correct
12 Correct 527 ms 143992 KB Output is correct
13 Correct 524 ms 143920 KB Output is correct
14 Correct 542 ms 143864 KB Output is correct
15 Correct 538 ms 143868 KB Output is correct
16 Correct 574 ms 143324 KB Output is correct
17 Correct 552 ms 143324 KB Output is correct
18 Correct 562 ms 143096 KB Output is correct
19 Correct 550 ms 143736 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 159828 KB Output is correct
2 Correct 328 ms 162188 KB Output is correct
3 Correct 325 ms 159852 KB Output is correct
4 Correct 451 ms 159864 KB Output is correct
5 Correct 433 ms 159928 KB Output is correct
6 Correct 426 ms 159344 KB Output is correct
7 Correct 428 ms 159144 KB Output is correct
8 Correct 424 ms 159224 KB Output is correct
9 Correct 435 ms 159352 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 124920 KB Output is correct
2 Correct 128 ms 124920 KB Output is correct
3 Correct 128 ms 124884 KB Output is correct
4 Correct 138 ms 124920 KB Output is correct
5 Correct 190 ms 124920 KB Output is correct
6 Correct 138 ms 124920 KB Output is correct
7 Correct 123 ms 124844 KB Output is correct
8 Correct 138 ms 124920 KB Output is correct
9 Correct 118 ms 124920 KB Output is correct
10 Correct 118 ms 124920 KB Output is correct
11 Correct 557 ms 143864 KB Output is correct
12 Correct 527 ms 143992 KB Output is correct
13 Correct 524 ms 143920 KB Output is correct
14 Correct 542 ms 143864 KB Output is correct
15 Correct 538 ms 143868 KB Output is correct
16 Correct 574 ms 143324 KB Output is correct
17 Correct 552 ms 143324 KB Output is correct
18 Correct 562 ms 143096 KB Output is correct
19 Correct 550 ms 143736 KB Output is correct
20 Correct 431 ms 159828 KB Output is correct
21 Correct 328 ms 162188 KB Output is correct
22 Correct 325 ms 159852 KB Output is correct
23 Correct 451 ms 159864 KB Output is correct
24 Correct 433 ms 159928 KB Output is correct
25 Correct 426 ms 159344 KB Output is correct
26 Correct 428 ms 159144 KB Output is correct
27 Correct 424 ms 159224 KB Output is correct
28 Correct 435 ms 159352 KB Output is correct
29 Correct 1930 ms 228936 KB Output is correct
30 Correct 1468 ms 233056 KB Output is correct
31 Correct 1539 ms 228984 KB Output is correct
32 Correct 2037 ms 228856 KB Output is correct
33 Correct 2069 ms 228904 KB Output is correct
34 Correct 1942 ms 226652 KB Output is correct
35 Correct 2005 ms 226396 KB Output is correct
36 Correct 1918 ms 226324 KB Output is correct
37 Correct 2069 ms 227664 KB Output is correct
38 Correct 1385 ms 234656 KB Output is correct
39 Correct 1385 ms 234572 KB Output is correct
40 Correct 1400 ms 231168 KB Output is correct
41 Correct 1390 ms 230608 KB Output is correct
42 Correct 1360 ms 230708 KB Output is correct
43 Correct 1389 ms 232344 KB Output is correct
44 Correct 1570 ms 233844 KB Output is correct
45 Correct 1583 ms 233952 KB Output is correct
46 Correct 1514 ms 230800 KB Output is correct
47 Correct 1568 ms 230472 KB Output is correct
48 Correct 1520 ms 230496 KB Output is correct
49 Correct 1531 ms 232604 KB Output is correct
50 Correct 1829 ms 231968 KB Output is correct
51 Correct 1652 ms 232056 KB Output is correct
52 Correct 1625 ms 229684 KB Output is correct
53 Correct 1738 ms 229212 KB Output is correct
54 Correct 1646 ms 229156 KB Output is correct
55 Correct 1635 ms 231032 KB Output is correct