oj.uz

Submission #950857

# Submission time Handle Problem Language Result Execution time Memory
950857 2024-03-20T19:50:42 Z pragmatist Triple Jump (JOI19_jumps) C++17
100 / 100
 919 ms 96340 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = (int)5e5+7;
const int M = (int)2e5+7;
const int inf = (int)1e9+7;

int n, q, a[N], b[N], ans[N];
pair<int, int> suf[N];
int L[N], R[N];
vector<pair<int, int> > Q[N];
vector<int> adj[N];

int add[4*N], t[4*N], mx[4*N];

void build(int v, int tl, int tr) {
	if(tl == tr) {
		t[v] = a[tl];
		return;
	}
	int mid = (tl+tr)/2;
	build(v*2, tl, mid);
	build(v*2+1, mid+1, tr);
	t[v] = max(t[v*2], t[v*2+1]);
	mx[v] = t[v];
}

void push(int v, int tl, int tr) {
	if(tl != tr) {
		add[v*2] = max(add[v*2], add[v]);
		add[v*2+1] = max(add[v*2+1], add[v]);
	}
	mx[v] = max(mx[v], t[v]+add[v]);
}

void upd(int v, int tl, int tr, int l, int r, int x) {
	push(v, tl, tr);
	if(tl>r || l>tr) {
		return;
	}
	if(tl >= l && tr<= r) {
		add[v] = max(add[v], x);
		push(v, tl, tr);
		return;
	}
	int mid = (tl+tr)>>1;
	upd(v*2, tl, mid, l, r, x);
	upd(v*2+1, mid+1, tr, l, r, x);
	mx[v] = max(mx[v*2], mx[v*2+1]);
}

void upd(int l, int r, int x) {
	if(l>r) {
		return;
	}
	upd(1, 1, n, l, r, x);
}

int get(int v, int tl, int tr, int l, int r) {
	push(v, tl, tr);
	if(tl >= l && tr <= r) {
		return mx[v];	
	}
	if(tl>r || l > tr) {
		return 0;
	}
	int mid = (tl+tr)/2;
	return max(get(v*2, tl, mid, l, r), get(v*2+1, mid+1, tr, l, r));
}

int get(int l, int r) {
    if(l>r) {
    	return 0;
    }
	return get(1, 1, n, l, r);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	} 
	build(1, 1, n);
	cin >> q;
    stack<int> st;
	for(int i = 1; i <= n; ++i) {
		L[i] = i;
		while(!st.empty() && a[st.top()]<a[i]) {
		    L[i]=L[st.top()];
			st.pop();
		}
		st.push(i);
	}
	while(!st.empty()) {
		continue;
	}
	for(int i = n; i >= 1; --i) {
		R[i] = i;
		while(!st.empty() && a[st.top()]<a[i]) {
			R[i] = R[st.top()];
			st.pop();
		}
		st.push(i);
	}
	for(int i = 1; i <= n; ++i) {
		if(R[i]+1<=n) {
			adj[i].push_back(R[i]+1);
		}
		if(L[i]-1>=1) {
			adj[L[i]-1].push_back(i);
		}
	}
    for(int i = 1; i <= q; ++i) {
    	int l, r;
    	cin >> l >> r;
		Q[l].push_back({r, i});		
    }          
    for(int l = n; l >= 1; --l) {
        {
        	for(int j : adj[l]) {
        		int i = l;
        		upd(2*j-i, n, a[i]+a[j]);		
        	}
        }
    	for(auto [r, i] : Q[l]) {
    		ans[i] = max(ans[i], get(l, r));
    	}
    }
    for(int i = 1; i <= q; ++i) {
    	cout << ans[i] << "\n";
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31064 KB Output is correct
2 Correct 7 ms 31068 KB Output is correct
3 Correct 7 ms 31236 KB Output is correct
4 Correct 6 ms 31068 KB Output is correct
5 Correct 7 ms 31068 KB Output is correct
6 Correct 7 ms 31068 KB Output is correct
7 Correct 6 ms 31068 KB Output is correct
8 Correct 6 ms 31068 KB Output is correct
9 Correct 7 ms 31264 KB Output is correct
10 Correct 6 ms 31064 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31064 KB Output is correct
2 Correct 7 ms 31068 KB Output is correct
3 Correct 7 ms 31236 KB Output is correct
4 Correct 6 ms 31068 KB Output is correct
5 Correct 7 ms 31068 KB Output is correct
6 Correct 7 ms 31068 KB Output is correct
7 Correct 6 ms 31068 KB Output is correct
8 Correct 6 ms 31068 KB Output is correct
9 Correct 7 ms 31264 KB Output is correct
10 Correct 6 ms 31064 KB Output is correct
11 Correct 249 ms 50048 KB Output is correct
12 Correct 233 ms 49980 KB Output is correct
13 Correct 246 ms 50376 KB Output is correct
14 Correct 236 ms 50004 KB Output is correct
15 Correct 244 ms 50512 KB Output is correct
16 Correct 243 ms 49464 KB Output is correct
17 Correct 248 ms 49336 KB Output is correct
18 Correct 267 ms 49212 KB Output is correct
19 Correct 250 ms 49808 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 47696 KB Output is correct
2 Correct 79 ms 48432 KB Output is correct
3 Correct 136 ms 47612 KB Output is correct
4 Correct 140 ms 47844 KB Output is correct
5 Correct 139 ms 47696 KB Output is correct
6 Correct 161 ms 47184 KB Output is correct
7 Correct 136 ms 46928 KB Output is correct
8 Correct 135 ms 46932 KB Output is correct
9 Correct 153 ms 47216 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31064 KB Output is correct
2 Correct 7 ms 31068 KB Output is correct
3 Correct 7 ms 31236 KB Output is correct
4 Correct 6 ms 31068 KB Output is correct
5 Correct 7 ms 31068 KB Output is correct
6 Correct 7 ms 31068 KB Output is correct
7 Correct 6 ms 31068 KB Output is correct
8 Correct 6 ms 31068 KB Output is correct
9 Correct 7 ms 31264 KB Output is correct
10 Correct 6 ms 31064 KB Output is correct
11 Correct 249 ms 50048 KB Output is correct
12 Correct 233 ms 49980 KB Output is correct
13 Correct 246 ms 50376 KB Output is correct
14 Correct 236 ms 50004 KB Output is correct
15 Correct 244 ms 50512 KB Output is correct
16 Correct 243 ms 49464 KB Output is correct
17 Correct 248 ms 49336 KB Output is correct
18 Correct 267 ms 49212 KB Output is correct
19 Correct 250 ms 49808 KB Output is correct
20 Correct 139 ms 47696 KB Output is correct
21 Correct 79 ms 48432 KB Output is correct
22 Correct 136 ms 47612 KB Output is correct
23 Correct 140 ms 47844 KB Output is correct
24 Correct 139 ms 47696 KB Output is correct
25 Correct 161 ms 47184 KB Output is correct
26 Correct 136 ms 46928 KB Output is correct
27 Correct 135 ms 46932 KB Output is correct
28 Correct 153 ms 47216 KB Output is correct
29 Correct 871 ms 90476 KB Output is correct
30 Correct 770 ms 92096 KB Output is correct
31 Correct 833 ms 90020 KB Output is correct
32 Correct 868 ms 90708 KB Output is correct
33 Correct 855 ms 90952 KB Output is correct
34 Correct 843 ms 88292 KB Output is correct
35 Correct 835 ms 88280 KB Output is correct
36 Correct 852 ms 88508 KB Output is correct
37 Correct 919 ms 89308 KB Output is correct
38 Correct 650 ms 96340 KB Output is correct
39 Correct 649 ms 96136 KB Output is correct
40 Correct 633 ms 92892 KB Output is correct
41 Correct 627 ms 92412 KB Output is correct
42 Correct 638 ms 92496 KB Output is correct
43 Correct 642 ms 94036 KB Output is correct
44 Correct 729 ms 95824 KB Output is correct
45 Correct 684 ms 95672 KB Output is correct
46 Correct 690 ms 92364 KB Output is correct
47 Correct 716 ms 92008 KB Output is correct
48 Correct 788 ms 91988 KB Output is correct
49 Correct 718 ms 94072 KB Output is correct
50 Correct 842 ms 93800 KB Output is correct
51 Correct 805 ms 93800 KB Output is correct
52 Correct 772 ms 91272 KB Output is correct
53 Correct 801 ms 90888 KB Output is correct
54 Correct 841 ms 90896 KB Output is correct
55 Correct 836 ms 92624 KB Output is correct