oj.uz

Submission #546827

# Submission time Handle Problem Language Result Execution time Memory
546827 2022-04-08T14:59:18 Z Arnch Triple Jump (JOI19_jumps) C++17
100 / 100
 1124 ms 148556 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define endl '\n'

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

int a[N], lm[N], rm[N], ansl[N], ansr[N], ans[N];
pair<int, int> p[N];
vector<int> query[N], st[N];

struct node {
	int ans, lz, mx = 0;
	node() {
		ans = lz = mx = 0;
	}
} x[N << 2];
void build(int l, int r, int v) {
	if(r - l < 2) {
		x[v].mx = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, 2 * v);
	build(mid, r, 2 * v + 1);
	x[v].mx = max(x[2 * v].mx, x[2 * v + 1].mx);
}
void put(int l, int r, int v) {
	x[2 * v].ans = max(x[2 * v].ans, x[v].lz + x[2 * v].mx);
	x[2 * v].lz = max(x[2 * v].lz, x[v].lz);
	x[2 * v + 1].ans = max(x[2 * v + 1].ans, x[v].lz + x[2 * v + 1].mx);
	x[2 * v + 1].lz = max(x[2 * v + 1].lz, x[v].lz);
}
void change(int l, int r, int s, int e, int val, int v) {
	if(r <= s || l >= e) return;
	if(l >= s && r <= e) {
		x[v].lz = max(x[v].lz, val);
		x[v].ans = max(x[v].ans, val + x[v].mx);
		return;
	}
	int mid = (l + r) / 2;
	put(l, r, v);
	change(l, mid, s, e, val, 2 * v);
	change(mid, r, s, e, val, 2 * v + 1);
	x[v].ans = max(x[v].lz + x[v].mx, max(x[2 * v].ans, x[2 * v + 1].ans));
}
int get(int l, int r, int s, int e, int v) {
	if(r <= s || l >= e) return 0;
	if(l >= s && r <= e) return x[v].ans;
	put(l, r, v);
	int mid = (l + r) >> 1;
	return max(get(l, mid, s, e, 2 * v), get(mid, r, s, e, 2 * v + 1));
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	int n; cin >>n;
	for(int i = 0; i < n; i++) {
		cin >>a[i];
	}
	int q; cin >>q;
	for(int i = 0; i < q; i++) {
		cin >>p[i].first >>p[i].second;
		p[i].first--, p[i].second--;
		query[p[i].first].push_back(i);
	}
		
	vector<int> vc;
	for(int i = 0; i < n; i++) {
		while(!vc.empty() && a[vc.back()] < a[i]) vc.pop_back();
		if(vc.empty()) lm[i] = -1;
		else lm[i] = vc.back();
		vc.push_back(i);
	}
	vc.clear();
	for(int i = n - 1; i >= 0; i--) {
		while(!vc.empty() && a[vc.back()] < a[i]) vc.pop_back();
		if(vc.empty()) rm[i] = n;
		else rm[i] = vc.back();
		vc.push_back(i);
	}

	build(0, n, 1);
	
	for(int i = n - 1; i >= 0; i--) {
		if(rm[i] != n) {
			int ind = rm[i] + (rm[i] - i);
			if(ind < n)
				change(0, n, ind, n, a[i] + a[rm[i]], 1);
		}
		for(auto j : st[i]) {
			change(0, n, j + (j - i), n, a[i] + a[j], 1);
		}
		if(lm[i] != -1) {
			int ind = i + (i - lm[i]);
			if(ind < n) {
				st[lm[i]].push_back(i);
			}
		}
		for(auto j : query[i]) {
			ans[j] = get(0, n, p[j].first, p[j].second + 1, 1);
		}
	}

	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 46 ms 94412 KB Output is correct
2 Correct 45 ms 94216 KB Output is correct
3 Correct 47 ms 94284 KB Output is correct
4 Correct 52 ms 94256 KB Output is correct
5 Correct 47 ms 94288 KB Output is correct
6 Correct 45 ms 94248 KB Output is correct
7 Correct 47 ms 94212 KB Output is correct
8 Correct 47 ms 94284 KB Output is correct
9 Correct 43 ms 94284 KB Output is correct
10 Correct 45 ms 94284 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94412 KB Output is correct
2 Correct 45 ms 94216 KB Output is correct
3 Correct 47 ms 94284 KB Output is correct
4 Correct 52 ms 94256 KB Output is correct
5 Correct 47 ms 94288 KB Output is correct
6 Correct 45 ms 94248 KB Output is correct
7 Correct 47 ms 94212 KB Output is correct
8 Correct 47 ms 94284 KB Output is correct
9 Correct 43 ms 94284 KB Output is correct
10 Correct 45 ms 94284 KB Output is correct
11 Correct 326 ms 113408 KB Output is correct
12 Correct 330 ms 113460 KB Output is correct
13 Correct 374 ms 113472 KB Output is correct
14 Correct 327 ms 113448 KB Output is correct
15 Correct 340 ms 113380 KB Output is correct
16 Correct 372 ms 112748 KB Output is correct
17 Correct 323 ms 112696 KB Output is correct
18 Correct 352 ms 112676 KB Output is correct
19 Correct 345 ms 113304 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 101504 KB Output is correct
2 Correct 124 ms 99256 KB Output is correct
3 Correct 142 ms 105412 KB Output is correct
4 Correct 213 ms 101680 KB Output is correct
5 Correct 187 ms 101504 KB Output is correct
6 Correct 212 ms 101032 KB Output is correct
7 Correct 198 ms 100848 KB Output is correct
8 Correct 189 ms 100732 KB Output is correct
9 Correct 189 ms 101200 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94412 KB Output is correct
2 Correct 45 ms 94216 KB Output is correct
3 Correct 47 ms 94284 KB Output is correct
4 Correct 52 ms 94256 KB Output is correct
5 Correct 47 ms 94288 KB Output is correct
6 Correct 45 ms 94248 KB Output is correct
7 Correct 47 ms 94212 KB Output is correct
8 Correct 47 ms 94284 KB Output is correct
9 Correct 43 ms 94284 KB Output is correct
10 Correct 45 ms 94284 KB Output is correct
11 Correct 326 ms 113408 KB Output is correct
12 Correct 330 ms 113460 KB Output is correct
13 Correct 374 ms 113472 KB Output is correct
14 Correct 327 ms 113448 KB Output is correct
15 Correct 340 ms 113380 KB Output is correct
16 Correct 372 ms 112748 KB Output is correct
17 Correct 323 ms 112696 KB Output is correct
18 Correct 352 ms 112676 KB Output is correct
19 Correct 345 ms 113304 KB Output is correct
20 Correct 198 ms 101504 KB Output is correct
21 Correct 124 ms 99256 KB Output is correct
22 Correct 142 ms 105412 KB Output is correct
23 Correct 213 ms 101680 KB Output is correct
24 Correct 187 ms 101504 KB Output is correct
25 Correct 212 ms 101032 KB Output is correct
26 Correct 198 ms 100848 KB Output is correct
27 Correct 189 ms 100732 KB Output is correct
28 Correct 189 ms 101200 KB Output is correct
29 Correct 1052 ms 139196 KB Output is correct
30 Correct 903 ms 133004 KB Output is correct
31 Correct 897 ms 148556 KB Output is correct
32 Correct 1058 ms 139048 KB Output is correct
33 Correct 1090 ms 139092 KB Output is correct
34 Correct 1049 ms 136828 KB Output is correct
35 Correct 1096 ms 136536 KB Output is correct
36 Correct 1062 ms 136456 KB Output is correct
37 Correct 1124 ms 137840 KB Output is correct
38 Correct 771 ms 145728 KB Output is correct
39 Correct 841 ms 145776 KB Output is correct
40 Correct 831 ms 142476 KB Output is correct
41 Correct 736 ms 141904 KB Output is correct
42 Correct 752 ms 141872 KB Output is correct
43 Correct 816 ms 143576 KB Output is correct
44 Correct 797 ms 145140 KB Output is correct
45 Correct 781 ms 145088 KB Output is correct
46 Correct 764 ms 141892 KB Output is correct
47 Correct 795 ms 141556 KB Output is correct
48 Correct 838 ms 141416 KB Output is correct
49 Correct 832 ms 143676 KB Output is correct
50 Correct 906 ms 142804 KB Output is correct
51 Correct 883 ms 142768 KB Output is correct
52 Correct 888 ms 140288 KB Output is correct
53 Correct 914 ms 139960 KB Output is correct
54 Correct 859 ms 140036 KB Output is correct
55 Correct 919 ms 141628 KB Output is correct