oj.uz

Submission #980613

# Submission time Handle Problem Language Result Execution time Memory
980613 2024-05-12T09:21:30 Z Dzadzo Triple Jump (JOI19_jumps) C++17
100 / 100
 988 ms 111096 KB 
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF LLONG_MAX
#define MOD 1000000007
#define MAXN 300000
using namespace std;
int t[4*MAXN+1],lazy[4*MAXN+1],ans[4*MAXN+1];
void build(int v,int tl,int tr,int a[]){
	if (tl==tr)t[v]=ans[v]=a[tl];else{
		int tm=(tl+tr)/2;
		build(v*2,tl,tm,a);
		build(v*2+1,tm+1,tr,a);
		t[v]=max(t[v*2],t[v*2+1]);
		ans[v]=max(ans[v*2],ans[v*2+1]);
	}
}
void push(int v){
	ans[2*v]=max(ans[2*v],t[2*v]+lazy[v]);
	ans[2*v+1]=max(ans[2*v+1],t[2*v+1]+lazy[v]);
	lazy[2*v]=max(lazy[2*v],lazy[v]);
	lazy[2*v+1]=max(lazy[2*v+1],lazy[v]);
	lazy[v]=0;
}
void up(int v,int tl,int tr,int l,int r,int delta){
	if (l>r)return;
	if (tl==l && tr==r){
		ans[v]=max(ans[v],t[v]+delta);
		lazy[v]=max(lazy[v],delta);
	}else{
		push(v);
		int tm=(tl+tr)/2;
		up(v*2,tl,tm,l,min(r,tm),delta);
		up(v*2+1,tm+1,tr,max(l,tm+1),r,delta);
		ans[v]=max(ans[2*v],ans[2*v+1]);
	}
}
int get(int v,int tl,int tr,int l,int r){
	if (l>r)return 0;
	if (tl==l && tr==r)return ans[v];
	push(v);
	int tm=(tl+tr)/2;
	return max(get(v*2,tl,tm,l,min(r,tm)),get(v*2+1,tm+1,tr,max(l,tm+1),r));
}
signed main(){	
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n;
	cin>>n;
	int a[n+1];
	for (int i=1;i<=n;i++)cin>>a[i];
	stack <int> s;
	vvi inds(n+1);
	for (int i=1;i<=n;i++){
		while (!s.empty() && a[s.top()]<a[i])s.pop();
		if (!s.empty()){
			if (2*i-s.top()<=n)inds[s.top()].pb(i);
		}
		s.push(i);
		inds[i].pb(i+1);
	}
	while(!s.empty())s.pop();
	for (int i=n;i>=1;i--){
		while (!s.empty() && a[s.top()]<a[i])s.pop();
		if (!s.empty()){
			if (2*s.top()-i<=n)inds[i].pb(s.top());
		}
		s.push(i);		
	}
	build(1,1,n,a);
	int q;
	cin>>q;
	vvp R(n+1);
	for (int i=1;i<=q;i++){
		int l,r;
		cin>>l>>r;
		R[l].pb({r,i});
	}
	int res[q+1];
	for (int i=n;i>=1;i--){
		for (int x:inds[i])up(1,1,n,2*x-i,n,a[x]+a[i]);
		for (auto &[r,id]:R[i])res[id]=get(1,1,n,i,r);
	}
	for (int i=1;i<=q;i++)cout<<res[i]<<'\n';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2508 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 239 ms 30164 KB Output is correct
12 Correct 243 ms 30100 KB Output is correct
13 Correct 231 ms 30164 KB Output is correct
14 Correct 217 ms 30132 KB Output is correct
15 Correct 221 ms 30296 KB Output is correct
16 Correct 220 ms 29524 KB Output is correct
17 Correct 232 ms 29712 KB Output is correct
18 Correct 220 ms 29304 KB Output is correct
19 Correct 236 ms 30080 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 37204 KB Output is correct
2 Correct 109 ms 35412 KB Output is correct
3 Correct 112 ms 35540 KB Output is correct
4 Correct 155 ms 37392 KB Output is correct
5 Correct 156 ms 37204 KB Output is correct
6 Correct 159 ms 36836 KB Output is correct
7 Correct 156 ms 36692 KB Output is correct
8 Correct 153 ms 36684 KB Output is correct
9 Correct 159 ms 36996 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2508 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 239 ms 30164 KB Output is correct
12 Correct 243 ms 30100 KB Output is correct
13 Correct 231 ms 30164 KB Output is correct
14 Correct 217 ms 30132 KB Output is correct
15 Correct 221 ms 30296 KB Output is correct
16 Correct 220 ms 29524 KB Output is correct
17 Correct 232 ms 29712 KB Output is correct
18 Correct 220 ms 29304 KB Output is correct
19 Correct 236 ms 30080 KB Output is correct
20 Correct 156 ms 37204 KB Output is correct
21 Correct 109 ms 35412 KB Output is correct
22 Correct 112 ms 35540 KB Output is correct
23 Correct 155 ms 37392 KB Output is correct
24 Correct 156 ms 37204 KB Output is correct
25 Correct 159 ms 36836 KB Output is correct
26 Correct 156 ms 36692 KB Output is correct
27 Correct 153 ms 36684 KB Output is correct
28 Correct 159 ms 36996 KB Output is correct
29 Correct 928 ms 107836 KB Output is correct
30 Correct 818 ms 105424 KB Output is correct
31 Correct 780 ms 101344 KB Output is correct
32 Correct 952 ms 107692 KB Output is correct
33 Correct 935 ms 107912 KB Output is correct
34 Correct 950 ms 105468 KB Output is correct
35 Correct 988 ms 105548 KB Output is correct
36 Correct 951 ms 105404 KB Output is correct
37 Correct 942 ms 106648 KB Output is correct
38 Correct 667 ms 110316 KB Output is correct
39 Correct 667 ms 110760 KB Output is correct
40 Correct 713 ms 107176 KB Output is correct
41 Correct 670 ms 106780 KB Output is correct
42 Correct 699 ms 106484 KB Output is correct
43 Correct 684 ms 108360 KB Output is correct
44 Correct 725 ms 110912 KB Output is correct
45 Correct 783 ms 110700 KB Output is correct
46 Correct 721 ms 107496 KB Output is correct
47 Correct 733 ms 107228 KB Output is correct
48 Correct 715 ms 107088 KB Output is correct
49 Correct 733 ms 109040 KB Output is correct
50 Correct 810 ms 111028 KB Output is correct
51 Correct 834 ms 111096 KB Output is correct
52 Correct 800 ms 108604 KB Output is correct
53 Correct 796 ms 108400 KB Output is correct
54 Correct 888 ms 108192 KB Output is correct
55 Correct 825 ms 109924 KB Output is correct