oj.uz

Submission #675993

# Submission time Handle Problem Language Result Execution time Memory
675993 2022-12-28T19:07:32 Z ghostwriter Triple Jump (JOI19_jumps) C++17
100 / 100
 1107 ms 104492 KB 
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
    #include <debug.h>
#else
    #define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
// #define int long long
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { T d2 = (a | b) & -(a | b); a /= d2; b /= d2; WHILE(b) { a = a % b; swap(a, b); } return a * d2; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
void _assert(bool statement) { if (statement) return; cerr << "\n>> Assertion failed!\n"; exit(0); }
void _assert(bool statement, const str &message) { if (statement) return; cerr << "\n>> Assertion failed: " << message << '\n'; exit(0); }
void _error(const str &message) { cerr << "\n>> Error: " << message << '\n'; exit(0); }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    GOAT
----------------------------------------------------------------
*/
const int N = 5e5 + 5;
int n, q, a[N];
pi query[N];
void input(int test_id) {
	cin >> n;
	FOR(i, 1, n) cin >> a[i];
	cin >> q;
	FOR(i, 1, q) cin >> query[i].st >> query[i].nd;
}
namespace subtask12 {
	const int N = 5005;
	int d[N][N], maxx[N], pos[N], rs = 0;
	int get(int l, int r) {
		if (!pos[l]) {
			maxx[l] = a[l];
			pos[l] = l;
		}
		WHILE(pos[l] < r) {
			++pos[l];
			maxx[l] = max(maxx[l], a[pos[l]]);
		}
		return maxx[l];
	}
	void solve() {
		FOR(len, 3, n)
		FOR(l, 1, n - len + 1) {
			int r = l + len - 1;
			d[l][r] = max({d[l + 1][r], d[l][r - 1], a[l] + a[r] + get(l + 1, l + (r - l) / 2)});
		}
		FOR(i, 1, q) {
			int l = query[i].st, r = query[i].nd;
			cout << d[l][r] << '\n';
		}
	}
}
namespace subtask3 {
	int maxx[N][18], LOG[N], rs = 0;
	multiset<pi> s;
	void build() {
		FOR(i, 1, n) {
			maxx[i][0] = a[i];
			LOG[i] = log2(i);
		}
		FOR(j, 1, 17)
		FOR(i, 1, n) {
			if (i + (1 << j) - 1 > n) break;
			maxx[i][j] = max(maxx[i][j - 1], maxx[i + (1 << (j - 1))][j - 1]);
		}
	}
	int get(int l, int r) {
		int l2 = LOG[r - l + 1];
		return max(maxx[l][l2], maxx[r - (1 << l2) + 1][l2]);
	}
	int cal(int i) {
		int rs = 0;
		FOR(j, 1, i - 2) {
			int mid = j + (i - j) / 2;
			rs = max(rs, a[j] + a[i] + get(j + 1, mid));
		}
		FOR(j, i + 2, n) {
			int mid = i + (j - i) / 2;
			rs = max(rs, a[i] + a[j] + get(i + 1, mid));
		}
		FOR(j, 1, i - 1)
			if (2 * i - j <= n)
				rs = max(rs, a[j] + a[i] + get(2 * i - j, n));
		return rs;
	}
	void solve() {
		FOR(i, 1, n) {
			s.ins({a[i], i});
			if (sz(s) > 18) s.ers(s.bg());
		}
		build();
		EACH(j, s) {
			int i = j.nd;
			rs = max(rs, cal(i));
		}
		cout << rs;
	}
}
namespace subtask4 {
	/*
		This is a tough problem, although I have a beautiful observation for subtask3 but still fall to the trap.
		Consider i and j, a[i] and a[j] must be bigger than every element that lies in [i + 1, j - 1] (as our claim) or else, we will
		move i (or j) to the position that is bigger than a[i] (or a[j]) and the cost won't change.
		What happen when we consider all pair i, j that sastified the condition? The answer is at most 2 * n. For all i, first we look at i - 1,
		after that the first element bigger than a[i - 1] and continue... This is familar? A standard deque trick (monotonic stack trick).
		The number of candidate pair (i, j) is at most 2 * n, now how to solve the problem with this observation is much more of a problem!
		I've seen some submission that use some tricks to avoid lazy propagate but I think it's too complicated so I'll use lazy propagate segtree to
		update and answer queries in a offline way.
		Upd: Nah, that lazy avoiding trick isn't that hard, it's just because I'm so high right now :v.
	*/
	const int oo = 5e8 + 5;
	struct Node {
		int ab, c, ans;
		Node() : ab(-oo), c(-oo), ans(-oo) {}
		Node(int ab, int c, int ans) : ab(ab), c(c), ans(ans) {}
	};
	const int T = 2e6 + 5;
	int qn[N], lp[N], ans[N];
	vpi a1;
	Node tr[T];
	Node comb(const Node &a, const Node &b) { return Node(max(a.ab, b.ab), max(a.c, b.c), max({a.ans, b.ans, a.ab + b.c})); }
	void upd(int i, int l, int r, int q, int v, bool type) {
		if (r < q || l > q) return;
		if (l == r) {
			if (!type) tr[i].c = max(tr[i].c, v);
			else tr[i] = Node(max(tr[i].ab, v), tr[i].c, max(tr[i].ans, v + tr[i].c));
			return;
		}
		int mid = l + (r - l) / 2;
		if (q <= mid) upd(i * 2, l, mid, q, v, type);
		else upd(i * 2 + 1, mid + 1, r, q, v, type);
		tr[i] = comb(tr[i * 2], tr[i * 2 + 1]);
	}
	Node get(int i, int l, int r, int ql, int qr) {
		if (r < ql || l > qr) return Node();
		if (ql <= l && r <= qr) return tr[i];
		int mid = l + (r - l) / 2;
		return comb(get(i * 2, l, mid, ql, qr), get(i * 2 + 1, mid + 1, r, ql, qr));
	}
	void solve() {
		FOR(i, 1, n) {
			int cur = i - 1;
			WHILE(cur) {
				a1.pb({cur, i});
				if (a[cur] > a[i]) {
					lp[i] = cur;
					break;
				}
				cur = lp[cur];
			}
		}
		sort(all(a1), [&](const pi &a, const pi &b) -> bool { return a.st > b.st; });
		FOR(i, 1, q) qn[i] = i;
		sort(qn + 1, qn + 1 + q, [&](const int &a, const int &b) { return query[a].st > query[b].st; });
		int cp = 0;
		FOR(i, 1, n) upd(1, 1, n, i, a[i], 0);
		FOR(j, 1, q) {
			int i = qn[j], l = query[i].st, r = query[i].nd;
			WHILE(cp < sz(a1) && a1[cp].st >= l) {
				upd(1, 1, n, 2 * a1[cp].nd - a1[cp].st, a[a1[cp].st] + a[a1[cp].nd], 1);
				++cp;
			}
			ans[i] = get(1, 1, n, l, r).ans;
		}
		FOR(i, 1, q) cout << ans[i] << '\n';
	}
}
void solve(int test_id) {
	if (n <= 5000) {
		subtask12::solve();
		return;
	}
	if (n <= 2e5 && q == 1 && query[1].st == 1 && query[1].nd == n) {
		subtask3::solve();
		return;
	}
	subtask4::solve();
}
void reinit(int test_id) {

}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    int test_num = 1;
    // cin >> test_num; // comment if the problem does not requires multitest
    FOR(i, 1, test_num) {
        input(i); // input in noninteractive problems for case #i
        solve(i); // main function to solve case #i
        reinit(i); // reinit global data to default used in case #i
    }
    #ifdef LOCAL
        cerr << "\nTime: " << setprecision(5) << fixed << (ldb)clock() / CLOCKS_PER_SEC << "ms.\n";
    #endif
    return 0;
}
/*
5
5 2 1 5 3
1
1 5
----------------------------------------------------------------
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 12 ms 24212 KB Output is correct
3 Correct 13 ms 24276 KB Output is correct
4 Correct 11 ms 24276 KB Output is correct
5 Correct 11 ms 24240 KB Output is correct
6 Correct 11 ms 24216 KB Output is correct
7 Correct 11 ms 24276 KB Output is correct
8 Correct 12 ms 24212 KB Output is correct
9 Correct 12 ms 24276 KB Output is correct
10 Correct 11 ms 24276 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 12 ms 24212 KB Output is correct
3 Correct 13 ms 24276 KB Output is correct
4 Correct 11 ms 24276 KB Output is correct
5 Correct 11 ms 24240 KB Output is correct
6 Correct 11 ms 24216 KB Output is correct
7 Correct 11 ms 24276 KB Output is correct
8 Correct 12 ms 24212 KB Output is correct
9 Correct 12 ms 24276 KB Output is correct
10 Correct 11 ms 24276 KB Output is correct
11 Correct 342 ms 104452 KB Output is correct
12 Correct 302 ms 104404 KB Output is correct
13 Correct 285 ms 104492 KB Output is correct
14 Correct 345 ms 104404 KB Output is correct
15 Correct 325 ms 104436 KB Output is correct
16 Correct 301 ms 103756 KB Output is correct
17 Correct 287 ms 103660 KB Output is correct
18 Correct 293 ms 103756 KB Output is correct
19 Correct 302 ms 104372 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 41228 KB Output is correct
2 Correct 88 ms 41188 KB Output is correct
3 Correct 77 ms 41216 KB Output is correct
4 Correct 80 ms 41224 KB Output is correct
5 Correct 82 ms 41212 KB Output is correct
6 Correct 80 ms 40480 KB Output is correct
7 Correct 79 ms 40464 KB Output is correct
8 Correct 81 ms 40344 KB Output is correct
9 Correct 83 ms 40740 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 12 ms 24212 KB Output is correct
3 Correct 13 ms 24276 KB Output is correct
4 Correct 11 ms 24276 KB Output is correct
5 Correct 11 ms 24240 KB Output is correct
6 Correct 11 ms 24216 KB Output is correct
7 Correct 11 ms 24276 KB Output is correct
8 Correct 12 ms 24212 KB Output is correct
9 Correct 12 ms 24276 KB Output is correct
10 Correct 11 ms 24276 KB Output is correct
11 Correct 342 ms 104452 KB Output is correct
12 Correct 302 ms 104404 KB Output is correct
13 Correct 285 ms 104492 KB Output is correct
14 Correct 345 ms 104404 KB Output is correct
15 Correct 325 ms 104436 KB Output is correct
16 Correct 301 ms 103756 KB Output is correct
17 Correct 287 ms 103660 KB Output is correct
18 Correct 293 ms 103756 KB Output is correct
19 Correct 302 ms 104372 KB Output is correct
20 Correct 79 ms 41228 KB Output is correct
21 Correct 88 ms 41188 KB Output is correct
22 Correct 77 ms 41216 KB Output is correct
23 Correct 80 ms 41224 KB Output is correct
24 Correct 82 ms 41212 KB Output is correct
25 Correct 80 ms 40480 KB Output is correct
26 Correct 79 ms 40464 KB Output is correct
27 Correct 81 ms 40344 KB Output is correct
28 Correct 83 ms 40740 KB Output is correct
29 Correct 1090 ms 59520 KB Output is correct
30 Correct 915 ms 53560 KB Output is correct
31 Correct 915 ms 55728 KB Output is correct
32 Correct 1107 ms 59600 KB Output is correct
33 Correct 1084 ms 59592 KB Output is correct
34 Correct 1091 ms 57244 KB Output is correct
35 Correct 1074 ms 56872 KB Output is correct
36 Correct 1077 ms 56828 KB Output is correct
37 Correct 1103 ms 58324 KB Output is correct
38 Correct 934 ms 59480 KB Output is correct
39 Correct 924 ms 59620 KB Output is correct
40 Correct 914 ms 56252 KB Output is correct
41 Correct 936 ms 55600 KB Output is correct
42 Correct 909 ms 55704 KB Output is correct
43 Correct 933 ms 57352 KB Output is correct
44 Correct 952 ms 59660 KB Output is correct
45 Correct 938 ms 59564 KB Output is correct
46 Correct 943 ms 56312 KB Output is correct
47 Correct 951 ms 56052 KB Output is correct
48 Correct 932 ms 55956 KB Output is correct
49 Correct 967 ms 58100 KB Output is correct
50 Correct 1022 ms 59560 KB Output is correct
51 Correct 1018 ms 59532 KB Output is correct
52 Correct 978 ms 57232 KB Output is correct
53 Correct 996 ms 56744 KB Output is correct
54 Correct 991 ms 56804 KB Output is correct
55 Correct 1008 ms 58436 KB Output is correct