oj.uz

Submission #318727

# Submission time Handle Problem Language Result Execution time Memory
318727 2020-11-03T03:32:35 Z aZvezda Triple Jump (JOI19_jumps) C++14
100 / 100
 1981 ms 117160 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const int MAX_N = 5e5 + 10;
int arr[MAX_N], n;
vector<pair<int, int> > cand, toAdd[MAX_N], queries[MAX_N];
int ans[MAX_N];

struct Node {
	int val, valFull, lazy;
	Node() {val = valFull = lazy = -mod;}
	Node operator +(const Node &other) const {
		Node ret;
		ret.val = max(val, other.val);
		ret.valFull = max(valFull, other.valFull);
		return ret;
	}
};

struct SegTree {
	Node tree[4 * MAX_N];
	void push(int curr, int l, int r) {
		chkmax(tree[curr].valFull, tree[curr].val + tree[curr].lazy);
		if(l != r) {
			chkmax(tree[curr * 2].lazy, tree[curr].lazy);
			chkmax(tree[curr * 2 + 1].lazy, tree[curr].lazy);
		}
		tree[curr].lazy = -mod;
	}
	void addToRoot(int x) {
		chkmax(tree[1].lazy, x);
	}
	int ans(int curr, int l, int r, int ql, int qr) {
		push(curr, l, r);
		if(ql <= l && r <= qr) {
			return tree[curr].valFull;
		} else if(ql > r || qr < l) {
			return 0;
		}
		int m = (l + r) / 2ll;
		return max(ans(curr * 2, l, m, ql, qr), ans(curr * 2 + 1, m + 1, r, ql, qr));
	}
	void upd(int curr, int l, int r, int ind, int val) {
		push(curr, l, r);
		if(l == r && l == ind) {
			chkmax(tree[curr].val, val);
			return;
		} else if(r < ind || l > ind) {
			return;
		}
		int m = (l + r) / 2ll;
		upd(curr * 2, l, m, ind, val);
		upd(curr * 2 + 1, m + 1, r, ind, val);
		tree[curr] = tree[curr * 2] + tree[curr * 2 + 1];
	}
};

SegTree seg;

signed main() {
	//ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for(int i = 0; i < n; i ++) {
		cin >> arr[i];
	}
	stack<int> st;
	for(int i = 0; i < n; i ++) {
		while(!st.empty() && arr[st.top()] < arr[i]) {
			st.pop();
		}
		if(!st.empty()) {
			cand.push_back({st.top(), i});
		}
		st.push(i);
	}
	while(!st.empty()) {st.pop();}
	for(int i = n - 1; i >= 0; i --) {
		while(!st.empty() && arr[st.top()] < arr[i]) {
			st.pop();
		}
		if(!st.empty()) {
			cand.push_back({i, st.top()});
		}
		st.push(i);
	}
	for(int i = 0; i < n - 1; i ++) {
		cand.push_back({i, i + 1});
	}
	for(auto it : cand) {
		if(it.second * 2 - it.first < n) {
			toAdd[it.second * 2 - it.first].push_back({arr[it.first] + arr[it.second], it.first});		
		}
	}
	
	int q;
	cin >> q;
	for(int i = 0; i < q; i ++) {
		int l, r;
		cin >> l >> r;
		queries[r - 1].push_back({l - 1, i});
	}

	for(int i = 0; i < n; i ++) {
		for(auto it : toAdd[i]) {
			seg.upd(1, 0, n - 1, it.second, it.first);
		}
		seg.addToRoot(arr[i]);
		for(auto it : queries[i]) {
			ans[it.second] = seg.ans(1, 0, n - 1, it.first, i);
		}
	}
	
	for(int i = 0; i < q; i ++) {
		cout << ans[i] << endl;
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47332 KB Output is correct
2 Correct 32 ms 47332 KB Output is correct
3 Correct 32 ms 47364 KB Output is correct
4 Correct 33 ms 47340 KB Output is correct
5 Correct 32 ms 47332 KB Output is correct
6 Correct 32 ms 47340 KB Output is correct
7 Correct 32 ms 47332 KB Output is correct
8 Correct 32 ms 47332 KB Output is correct
9 Correct 32 ms 47340 KB Output is correct
10 Correct 31 ms 47340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47332 KB Output is correct
2 Correct 32 ms 47332 KB Output is correct
3 Correct 32 ms 47364 KB Output is correct
4 Correct 33 ms 47340 KB Output is correct
5 Correct 32 ms 47332 KB Output is correct
6 Correct 32 ms 47340 KB Output is correct
7 Correct 32 ms 47332 KB Output is correct
8 Correct 32 ms 47332 KB Output is correct
9 Correct 32 ms 47340 KB Output is correct
10 Correct 31 ms 47340 KB Output is correct
11 Correct 578 ms 61768 KB Output is correct
12 Correct 541 ms 61412 KB Output is correct
13 Correct 562 ms 61412 KB Output is correct
14 Correct 562 ms 61668 KB Output is correct
15 Correct 556 ms 61540 KB Output is correct
16 Correct 559 ms 61028 KB Output is correct
17 Correct 554 ms 61156 KB Output is correct
18 Correct 551 ms 60900 KB Output is correct
19 Correct 553 ms 61596 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 62652 KB Output is correct
2 Correct 255 ms 58320 KB Output is correct
3 Correct 260 ms 57552 KB Output is correct
4 Correct 365 ms 62652 KB Output is correct
5 Correct 367 ms 62524 KB Output is correct
6 Correct 341 ms 62748 KB Output is correct
7 Correct 338 ms 62532 KB Output is correct
8 Correct 340 ms 62524 KB Output is correct
9 Correct 346 ms 62652 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47332 KB Output is correct
2 Correct 32 ms 47332 KB Output is correct
3 Correct 32 ms 47364 KB Output is correct
4 Correct 33 ms 47340 KB Output is correct
5 Correct 32 ms 47332 KB Output is correct
6 Correct 32 ms 47340 KB Output is correct
7 Correct 32 ms 47332 KB Output is correct
8 Correct 32 ms 47332 KB Output is correct
9 Correct 32 ms 47340 KB Output is correct
10 Correct 31 ms 47340 KB Output is correct
11 Correct 578 ms 61768 KB Output is correct
12 Correct 541 ms 61412 KB Output is correct
13 Correct 562 ms 61412 KB Output is correct
14 Correct 562 ms 61668 KB Output is correct
15 Correct 556 ms 61540 KB Output is correct
16 Correct 559 ms 61028 KB Output is correct
17 Correct 554 ms 61156 KB Output is correct
18 Correct 551 ms 60900 KB Output is correct
19 Correct 553 ms 61596 KB Output is correct
20 Correct 368 ms 62652 KB Output is correct
21 Correct 255 ms 58320 KB Output is correct
22 Correct 260 ms 57552 KB Output is correct
23 Correct 365 ms 62652 KB Output is correct
24 Correct 367 ms 62524 KB Output is correct
25 Correct 341 ms 62748 KB Output is correct
26 Correct 338 ms 62532 KB Output is correct
27 Correct 340 ms 62524 KB Output is correct
28 Correct 346 ms 62652 KB Output is correct
29 Correct 1948 ms 106920 KB Output is correct
30 Correct 1595 ms 102844 KB Output is correct
31 Correct 1655 ms 100692 KB Output is correct
32 Correct 1981 ms 111272 KB Output is correct
33 Correct 1946 ms 111272 KB Output is correct
34 Correct 1911 ms 109060 KB Output is correct
35 Correct 1939 ms 108776 KB Output is correct
36 Correct 1962 ms 108748 KB Output is correct
37 Correct 1952 ms 110196 KB Output is correct
38 Correct 1574 ms 117032 KB Output is correct
39 Correct 1567 ms 117160 KB Output is correct
40 Correct 1491 ms 113752 KB Output is correct
41 Correct 1484 ms 113388 KB Output is correct
42 Correct 1466 ms 113216 KB Output is correct
43 Correct 1507 ms 115120 KB Output is correct
44 Correct 1610 ms 116308 KB Output is correct
45 Correct 1611 ms 116484 KB Output is correct
46 Correct 1539 ms 113404 KB Output is correct
47 Correct 1544 ms 113180 KB Output is correct
48 Correct 1539 ms 112804 KB Output is correct
49 Correct 1549 ms 114984 KB Output is correct
50 Correct 1693 ms 114524 KB Output is correct
51 Correct 1681 ms 114604 KB Output is correct
52 Correct 1628 ms 112172 KB Output is correct
53 Correct 1619 ms 111784 KB Output is correct
54 Correct 1627 ms 111780 KB Output is correct
55 Correct 1673 ms 113448 KB Output is correct