oj.uz

Submission #1118827

# Submission time Handle Problem Language Result Execution time Memory
1118827 2024-11-26T08:18:47 Z Dan4Life Triple Jump (JOI19_jumps) C++17
100 / 100
 1557 ms 133768 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
using ar2 = array<int,2>;
const int N = (int)1e6+10;
const int INF = (int)1e18;
int n, q, a[N], ans[N];
vector<ar2> v[N], Q[N];
stack<int> S;

struct Data{ int mxSm, mxA, ans;} seg[2*N];

Data comb(Data a, Data b){
	Data c;
	c.mxSm = max(a.mxSm, b.mxSm);
	c.mxA = max(a.mxA, b.mxA);
	c.ans = max({a.ans,b.ans,a.mxSm+b.mxA});
	return c;
}

void upd(int x, int v, int p=0, int l=1, int r=n){
	if(l==r){ 
		seg[p].mxSm = max(seg[p].mxSm, v);
		seg[p].mxA = max(seg[p].mxA,a[x]); 
		seg[p].ans = seg[p].mxSm+seg[p].mxA;
		return;
	}
	int mid = (l+r)/2; int rp = p+2*(mid-l+1);
	if(x<=mid) upd(x,v,p+1,l,mid);
	else upd(x,v,rp,mid+1,r);
	seg[p] = comb(seg[p+1],seg[rp]);
}

Data query(int i, int j, int p=0, int l=1, int r=n){
	if(i>r or j<l or i>j) return {-INF,-INF,-INF};
	if(i<=l and r<=j) return seg[p];
	int mid = (l+r)/2; int rp = p+2*(mid-l+1);
	return comb(query(i,j,p+1,l,mid),query(i,j,rp,mid+1,r));
}

int32_t main(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = n,j; i >= 1; i--){
		while(sz(S) and a[S.top()]<a[i])
			j = S.top(), v[i].pb({j,a[i]+a[j]}),S.pop();
		if(sz(S)) j = S.top(), v[i].pb({j,a[i]+a[j]});
		S.push(i);
	}
	cin >> q;
	for(int l,r,i=1; i <= q; i++)
		cin >> l >> r, Q[l].pb({r,i});
	for(int i = n; i >= 1; i--){
		for(auto [j,sum] : v[i]) if(2*j-i<=n) upd(2*j-i,sum);
		for(auto [j,ind] : Q[i]) ans[ind] = query(i,j).ans;
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47176 KB Output is correct
2 Correct 36 ms 47440 KB Output is correct
3 Correct 33 ms 47208 KB Output is correct
4 Correct 47 ms 47308 KB Output is correct
5 Correct 43 ms 47260 KB Output is correct
6 Correct 32 ms 47440 KB Output is correct
7 Correct 38 ms 47440 KB Output is correct
8 Correct 35 ms 47440 KB Output is correct
9 Correct 39 ms 47440 KB Output is correct
10 Correct 34 ms 47288 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47176 KB Output is correct
2 Correct 36 ms 47440 KB Output is correct
3 Correct 33 ms 47208 KB Output is correct
4 Correct 47 ms 47308 KB Output is correct
5 Correct 43 ms 47260 KB Output is correct
6 Correct 32 ms 47440 KB Output is correct
7 Correct 38 ms 47440 KB Output is correct
8 Correct 35 ms 47440 KB Output is correct
9 Correct 39 ms 47440 KB Output is correct
10 Correct 34 ms 47288 KB Output is correct
11 Correct 488 ms 74604 KB Output is correct
12 Correct 441 ms 74708 KB Output is correct
13 Correct 448 ms 74824 KB Output is correct
14 Correct 437 ms 74632 KB Output is correct
15 Correct 383 ms 74056 KB Output is correct
16 Correct 436 ms 74168 KB Output is correct
17 Correct 425 ms 69704 KB Output is correct
18 Correct 507 ms 73172 KB Output is correct
19 Correct 464 ms 72904 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 70232 KB Output is correct
2 Correct 154 ms 67144 KB Output is correct
3 Correct 158 ms 66120 KB Output is correct
4 Correct 225 ms 70152 KB Output is correct
5 Correct 236 ms 70028 KB Output is correct
6 Correct 228 ms 69704 KB Output is correct
7 Correct 206 ms 69448 KB Output is correct
8 Correct 222 ms 69628 KB Output is correct
9 Correct 226 ms 69704 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47176 KB Output is correct
2 Correct 36 ms 47440 KB Output is correct
3 Correct 33 ms 47208 KB Output is correct
4 Correct 47 ms 47308 KB Output is correct
5 Correct 43 ms 47260 KB Output is correct
6 Correct 32 ms 47440 KB Output is correct
7 Correct 38 ms 47440 KB Output is correct
8 Correct 35 ms 47440 KB Output is correct
9 Correct 39 ms 47440 KB Output is correct
10 Correct 34 ms 47288 KB Output is correct
11 Correct 488 ms 74604 KB Output is correct
12 Correct 441 ms 74708 KB Output is correct
13 Correct 448 ms 74824 KB Output is correct
14 Correct 437 ms 74632 KB Output is correct
15 Correct 383 ms 74056 KB Output is correct
16 Correct 436 ms 74168 KB Output is correct
17 Correct 425 ms 69704 KB Output is correct
18 Correct 507 ms 73172 KB Output is correct
19 Correct 464 ms 72904 KB Output is correct
20 Correct 226 ms 70232 KB Output is correct
21 Correct 154 ms 67144 KB Output is correct
22 Correct 158 ms 66120 KB Output is correct
23 Correct 225 ms 70152 KB Output is correct
24 Correct 236 ms 70028 KB Output is correct
25 Correct 228 ms 69704 KB Output is correct
26 Correct 206 ms 69448 KB Output is correct
27 Correct 222 ms 69628 KB Output is correct
28 Correct 226 ms 69704 KB Output is correct
29 Correct 1557 ms 131000 KB Output is correct
30 Correct 1047 ms 124956 KB Output is correct
31 Correct 1090 ms 122716 KB Output is correct
32 Correct 1413 ms 127932 KB Output is correct
33 Correct 1385 ms 130816 KB Output is correct
34 Correct 1336 ms 126620 KB Output is correct
35 Correct 1381 ms 126536 KB Output is correct
36 Correct 1265 ms 126548 KB Output is correct
37 Correct 1209 ms 127416 KB Output is correct
38 Correct 961 ms 130628 KB Output is correct
39 Correct 1086 ms 130744 KB Output is correct
40 Correct 1046 ms 128272 KB Output is correct
41 Correct 1025 ms 130120 KB Output is correct
42 Correct 962 ms 127816 KB Output is correct
43 Correct 1046 ms 129168 KB Output is correct
44 Correct 1058 ms 133768 KB Output is correct
45 Correct 1074 ms 125236 KB Output is correct
46 Correct 1046 ms 123656 KB Output is correct
47 Correct 1081 ms 132220 KB Output is correct
48 Correct 1070 ms 127632 KB Output is correct
49 Correct 1077 ms 124808 KB Output is correct
50 Correct 1284 ms 130788 KB Output is correct
51 Correct 1153 ms 131376 KB Output is correct
52 Correct 1111 ms 124772 KB Output is correct
53 Correct 1177 ms 133460 KB Output is correct
54 Correct 1182 ms 131472 KB Output is correct
55 Correct 1139 ms 125596 KB Output is correct