oj.uz

Submission #1117913

# Submission time Handle Problem Language Result Execution time Memory
1117913 2024-11-24T09:57:14 Z XRomanticCatX Triple Jump (JOI19_jumps) C++17
100 / 100
 1637 ms 139252 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long int
#define pii pair<int , int>
#define f first
#define s second

const int MAXN = 1e6 + 5;

const int MOD = (119 >> 23) ^ 1;

const int INF = 1e10;

int p = 1;

struct segment{
	int val[MAXN * 2];
	int seg[MAXN * 2];
	int lazy[MAXN * 2];
	segment(){
		for(int i = 1 ; i < MAXN * 2 ; i++){
			val[i] = 0;
			seg[i] = 0;
			lazy[i] = 0;
		}
	}
	void build(){
		for(int i = p - 1 ; i >= 1 ; i--){
			val[i] = max(val[i * 2] , val[i * 2 + 1]);
		}
	}
	int getmax(int v , int vl , int vr , int l , int r){
		if(vr < l || r < vl) return 0;
		if(vl >= l && vr <= r) return val[v];
		int mid = (vr + vl) >> 1;
		return max(getmax(v * 2 , vl , mid , l , r) , getmax(v * 2 + 1 , mid + 1 , vr , l , r));
	}
	void shift(int v){
		if(v >= p) return;
		lazy[v * 2] = max(lazy[v * 2] , lazy[v]);
		lazy[v * 2 + 1] = max(lazy[v * 2 + 1] , lazy[v]);
		seg[v * 2] = max(seg[v * 2] , lazy[v] + val[v * 2]);
		seg[v * 2 + 1] = max(seg[v * 2 + 1] , lazy[v] + val[v * 2 + 1]);
		lazy[v] = 0;
	}
	void update(int v , int vl , int vr , int l , int r , int x){
		if(vr < l || r < vl) return;
		if(vl >= l && vr <= r){
			lazy[v] = max(lazy[v] , x);
			seg[v] = max(seg[v] , x + val[v]);
			return;
		}
		shift(v);
		int mid = (vr + vl) >> 1;
		update(v * 2 , vl , mid , l , r , x);
		update(v * 2 + 1 , mid + 1 , vr , l , r , x);
		seg[v] = max(seg[v * 2] , seg[v * 2 + 1]); 
	}
	int getans(int v , int vl , int vr , int l , int r){
		if(vr < l || r < vl) return 0;
		if(vl >= l && vr <= r) return seg[v];
		shift(v);
		int mid = (vr + vl) >> 1;
		return max(getans(v * 2 , vl , mid , l , r) , getans(v * 2 + 1 , mid + 1 , vr , l , r));
	}
};

segment tree;

signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0) ,cout.tie(0);
	int n;
	cin>>n;
	while(p < n) p *= 2;
	int a[n + 5];
	for(int i = 1 ; i <= n ; i++){
		cin>>a[i];
		tree.val[i + p] = a[i];
	}
	tree.build();
	int lef[n + 5];
	int rig[n + 5];
	stack <pii> st;
	st.push({INF , 0});
	for(int i = 1 ; i <= n ; i++){
		while(!st.empty() and a[i] > st.top().f){
			st.pop();
		}
		lef[i] = st.top().s;
		st.push({a[i] , i});
	}
	stack <pii> stt;
	stt.push({INF , n + 1});
	for(int i = n ; i >= 1 ; i--){
		while(!stt.empty() and a[i] > stt.top().f){
			stt.pop();
		}
		rig[i] = stt.top().s;
		stt.push({a[i] , i});
	}
	vector <int> update[n + 5];
	vector <pii> query[n + 5];
	for(int i = n ; i >= 1 ; i--){
		if(lef[i]) update[lef[i]].push_back(i);
		if(rig[i] <= n) update[i].push_back(rig[i]); 
	}	
	int q;
	cin>>q;
	int fq = q;
	while(q--){
		int l , r;
		cin>>l>>r;
		query[l].push_back({r , fq - q});
	}
	int ans[fq + 5];
	for(int i = n - 1 ; i >= 1 ; i--){
		for(auto u : update[i]){
			tree.update(1 , 0 , p - 1 , u + u - i , n , a[i] + a[u]);
		}
		for(auto u : query[i]){
			ans[u.s] = tree.getans(1 , 0 , p - 1 , i , u.f);
		}
	}
	for(int i = 1 ; i <= fq ; i++){
		cout<<ans[i]<<endl;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47184 KB Output is correct
2 Correct 7 ms 47184 KB Output is correct
3 Correct 7 ms 47440 KB Output is correct
4 Correct 8 ms 47184 KB Output is correct
5 Correct 7 ms 47184 KB Output is correct
6 Correct 7 ms 47184 KB Output is correct
7 Correct 8 ms 47420 KB Output is correct
8 Correct 7 ms 47424 KB Output is correct
9 Correct 7 ms 47440 KB Output is correct
10 Correct 8 ms 47184 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47184 KB Output is correct
2 Correct 7 ms 47184 KB Output is correct
3 Correct 7 ms 47440 KB Output is correct
4 Correct 8 ms 47184 KB Output is correct
5 Correct 7 ms 47184 KB Output is correct
6 Correct 7 ms 47184 KB Output is correct
7 Correct 8 ms 47420 KB Output is correct
8 Correct 7 ms 47424 KB Output is correct
9 Correct 7 ms 47440 KB Output is correct
10 Correct 8 ms 47184 KB Output is correct
11 Correct 873 ms 74852 KB Output is correct
12 Correct 857 ms 74824 KB Output is correct
13 Correct 846 ms 74828 KB Output is correct
14 Correct 883 ms 74928 KB Output is correct
15 Correct 854 ms 74820 KB Output is correct
16 Correct 842 ms 74312 KB Output is correct
17 Correct 851 ms 74312 KB Output is correct
18 Correct 853 ms 74144 KB Output is correct
19 Correct 845 ms 74756 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 68984 KB Output is correct
2 Correct 109 ms 71096 KB Output is correct
3 Correct 108 ms 70984 KB Output is correct
4 Correct 180 ms 68936 KB Output is correct
5 Correct 185 ms 68936 KB Output is correct
6 Correct 176 ms 69960 KB Output is correct
7 Correct 182 ms 69968 KB Output is correct
8 Correct 183 ms 69960 KB Output is correct
9 Correct 190 ms 70216 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47184 KB Output is correct
2 Correct 7 ms 47184 KB Output is correct
3 Correct 7 ms 47440 KB Output is correct
4 Correct 8 ms 47184 KB Output is correct
5 Correct 7 ms 47184 KB Output is correct
6 Correct 7 ms 47184 KB Output is correct
7 Correct 8 ms 47420 KB Output is correct
8 Correct 7 ms 47424 KB Output is correct
9 Correct 7 ms 47440 KB Output is correct
10 Correct 8 ms 47184 KB Output is correct
11 Correct 873 ms 74852 KB Output is correct
12 Correct 857 ms 74824 KB Output is correct
13 Correct 846 ms 74828 KB Output is correct
14 Correct 883 ms 74928 KB Output is correct
15 Correct 854 ms 74820 KB Output is correct
16 Correct 842 ms 74312 KB Output is correct
17 Correct 851 ms 74312 KB Output is correct
18 Correct 853 ms 74144 KB Output is correct
19 Correct 845 ms 74756 KB Output is correct
20 Correct 181 ms 68984 KB Output is correct
21 Correct 109 ms 71096 KB Output is correct
22 Correct 108 ms 70984 KB Output is correct
23 Correct 180 ms 68936 KB Output is correct
24 Correct 185 ms 68936 KB Output is correct
25 Correct 176 ms 69960 KB Output is correct
26 Correct 182 ms 69968 KB Output is correct
27 Correct 183 ms 69960 KB Output is correct
28 Correct 190 ms 70216 KB Output is correct
29 Correct 1615 ms 134176 KB Output is correct
30 Correct 1400 ms 139252 KB Output is correct
31 Correct 1478 ms 139224 KB Output is correct
32 Correct 1637 ms 134220 KB Output is correct
33 Correct 1582 ms 134216 KB Output is correct
34 Correct 1580 ms 131976 KB Output is correct
35 Correct 1562 ms 131632 KB Output is correct
36 Correct 1570 ms 131688 KB Output is correct
37 Correct 1569 ms 133008 KB Output is correct
38 Correct 1395 ms 136784 KB Output is correct
39 Correct 1412 ms 136808 KB Output is correct
40 Correct 1491 ms 133612 KB Output is correct
41 Correct 1387 ms 133092 KB Output is correct
42 Correct 1384 ms 132932 KB Output is correct
43 Correct 1419 ms 134748 KB Output is correct
44 Correct 1472 ms 137152 KB Output is correct
45 Correct 1377 ms 137032 KB Output is correct
46 Correct 1488 ms 133884 KB Output is correct
47 Correct 1454 ms 133640 KB Output is correct
48 Correct 1398 ms 133576 KB Output is correct
49 Correct 1427 ms 135460 KB Output is correct
50 Correct 1487 ms 137332 KB Output is correct
51 Correct 1543 ms 137292 KB Output is correct
52 Correct 1530 ms 134968 KB Output is correct
53 Correct 1474 ms 134508 KB Output is correct
54 Correct 1481 ms 134668 KB Output is correct
55 Correct 1523 ms 136308 KB Output is correct