oj.uz

Submission #944315

# Submission time Handle Problem Language Result Execution time Memory
944315 2024-03-12T14:36:27 Z LCJLY Triple Jump (JOI19_jumps) C++14
100 / 100
 888 ms 155636 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int arr[500005];
struct node{
	int s,e,m;
	node *l,*r;
	int v,lazyMax,hold;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0),lazyMax(0),hold(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			v=max(l->v,r->v);
		}
		else v=arr[s];
	}
	
	void self_change(int x){
		lazyMax=max(lazyMax,x);
		hold=max(hold,v+x);
	}
	
	void forceProp(){
		if(s==e) return;
		l->self_change(lazyMax);
		r->self_change(lazyMax);
	}
	
	void rangeUpd(int x, int y, int c){
		if(x>y) return;
		if(x<=s&&y>=e){
			self_change(c);
			return;
		}
		forceProp();
		if(x<=m) l->rangeUpd(x,y,c);
		if(y>m) r->rangeUpd(x,y,c);
		hold=max(l->hold,r->hold);
	}
	
	int query(int x, int y){
		if(x<=s&&y>=e) return hold;
		forceProp();
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return max(l->query(x,m),r->query(m+1,y));
	}
};

void solve(){
	int n;
	cin >> n;
	for(int x=1;x<=n;x++){
		cin >> arr[x];
	}
	
	vector<int>adj[n+5];
	deque<int>d;
	for(int x=1;x<=n;x++){
		while(!d.empty()&&arr[d.back()]<arr[x]) d.pop_back();
		if(!d.empty()){
			adj[d.back()].push_back(x);
		}
		d.push_back(x);
	}
	
	d.clear();
	for(int x=n;x>=1;x--){
		while(!d.empty()&&arr[d.back()]<arr[x]) d.pop_back();
		if(!d.empty()){
			adj[x].push_back(d.back());
		}
		d.push_back(x);
	}
	
	node st(0,n);
	
	int q;
	cin >> q;
	vector<pii>que[n+5];
	int temp,temp2;
	for(int x=0;x<q;x++){
		cin >> temp >> temp2;
		que[temp].push_back({temp2,x});
	}
	
	int ans[q];
	
	for(int x=n;x>=1;x--){
		for(auto it:adj[x]){
			int hold=arr[it]+arr[x];
			//show2(2*it-x,2*it-x,hold,hold);
			st.rangeUpd(2*it-x,n,hold);
		}
		for(auto it:que[x]){
			int index=it.second;
			int r=it.first;
			ans[index]=st.query(x,r);
		}
		
		//for(int y=1;y<=n;y++){
			//cout << st.query(y,y) << " ";
 		//}
 		//cout <<  " st" << endl;
	}
	
	for(int x=0;x<q;x++){
		cout << ans[x] << "\n";
	}	
}	

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 190 ms 24868 KB Output is correct
12 Correct 180 ms 25172 KB Output is correct
13 Correct 181 ms 25228 KB Output is correct
14 Correct 177 ms 25072 KB Output is correct
15 Correct 182 ms 25436 KB Output is correct
16 Correct 208 ms 24660 KB Output is correct
17 Correct 188 ms 24936 KB Output is correct
18 Correct 181 ms 24408 KB Output is correct
19 Correct 189 ms 25476 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 51492 KB Output is correct
2 Correct 76 ms 51632 KB Output is correct
3 Correct 77 ms 50120 KB Output is correct
4 Correct 114 ms 51204 KB Output is correct
5 Correct 116 ms 51188 KB Output is correct
6 Correct 118 ms 51008 KB Output is correct
7 Correct 113 ms 50992 KB Output is correct
8 Correct 110 ms 50832 KB Output is correct
9 Correct 111 ms 51028 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 190 ms 24868 KB Output is correct
12 Correct 180 ms 25172 KB Output is correct
13 Correct 181 ms 25228 KB Output is correct
14 Correct 177 ms 25072 KB Output is correct
15 Correct 182 ms 25436 KB Output is correct
16 Correct 208 ms 24660 KB Output is correct
17 Correct 188 ms 24936 KB Output is correct
18 Correct 181 ms 24408 KB Output is correct
19 Correct 189 ms 25476 KB Output is correct
20 Correct 127 ms 51492 KB Output is correct
21 Correct 76 ms 51632 KB Output is correct
22 Correct 77 ms 50120 KB Output is correct
23 Correct 114 ms 51204 KB Output is correct
24 Correct 116 ms 51188 KB Output is correct
25 Correct 118 ms 51008 KB Output is correct
26 Correct 113 ms 50992 KB Output is correct
27 Correct 110 ms 50832 KB Output is correct
28 Correct 111 ms 51028 KB Output is correct
29 Correct 874 ms 149704 KB Output is correct
30 Correct 725 ms 150648 KB Output is correct
31 Correct 749 ms 146568 KB Output is correct
32 Correct 869 ms 149768 KB Output is correct
33 Correct 834 ms 149752 KB Output is correct
34 Correct 828 ms 148832 KB Output is correct
35 Correct 887 ms 148448 KB Output is correct
36 Correct 888 ms 148368 KB Output is correct
37 Correct 841 ms 149300 KB Output is correct
38 Correct 496 ms 152132 KB Output is correct
39 Correct 505 ms 152108 KB Output is correct
40 Correct 494 ms 150364 KB Output is correct
41 Correct 488 ms 149808 KB Output is correct
42 Correct 494 ms 149920 KB Output is correct
43 Correct 506 ms 150888 KB Output is correct
44 Correct 551 ms 152660 KB Output is correct
45 Correct 581 ms 155160 KB Output is correct
46 Correct 550 ms 152912 KB Output is correct
47 Correct 533 ms 152780 KB Output is correct
48 Correct 581 ms 152880 KB Output is correct
49 Correct 531 ms 154396 KB Output is correct
50 Correct 622 ms 155636 KB Output is correct
51 Correct 628 ms 155628 KB Output is correct
52 Correct 617 ms 153868 KB Output is correct
53 Correct 616 ms 153620 KB Output is correct
54 Correct 663 ms 153680 KB Output is correct
55 Correct 617 ms 154948 KB Output is correct