oj.uz

Submission #528905

# Submission time Handle Problem Language Result Execution time Memory
528905 2022-02-21T17:47:12 Z Koosha_mv Triple Jump (JOI19_jumps) C++14
100 / 100
 1038 ms 122128 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int N=5e5+99,xn=N<<2,inf=1e10;

int n,m,a[N],ans[N],seg[xn],lazy[xn],Mx[xn];
int L[N],R[N];
vector<int> vec[N];
vector<pair<int,int>> Q[N];

void shift(int ,int ,int );

void upd(int id){
	Mx[id]=max(Mx[id<<1],Mx[id<<1|1]);
	seg[id]=max(seg[id<<1],seg[id<<1|1]);
}
void find(){
	a[0]=inf;
	a[n+1]=inf;
	f(i,1,n+1){
		L[i]=i-1;
		while(a[L[i]]<a[i]){
			L[i]=L[L[i]];
		}
		if(0<L[i]) vec[L[i]].pb(i);
	}
	f_(i,n,1){
		R[i]=i+1;
		while(a[R[i]]<a[i]){
			R[i]=R[R[i]];
		}
		if(R[i]<=n) vec[i].pb(R[i]);
	}
}
void build(int id=1,int l=1,int r=n+1){
	if(l+1==r){
		Mx[id]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid,r);
	upd(id);
}
void update(int L,int R,int val,int id=1,int l=1,int r=n+1){
	if(r<=L || R<=l) return ;
	if(L<=l && r<=R){
		maxm(lazy[id],val);
		maxm(seg[id],Mx[id]+val);
		return ;
	}
	int mid=(l+r)>>1;
	shift(id,l,r);
	update(L,R,val,id<<1,l,mid);
	update(L,R,val,id<<1|1,mid,r);
	upd(id);
}
int query(int L,int R,int id=1,int l=1,int r=n+1){
	if(r<=L || R<=l) return -inf;
	if(L<=l && r<=R){
		return seg[id];
	}
	int mid=(l+r)>>1;
	shift(id,l,r);
	return max(query(L,R,id<<1,l,mid),query(L,R,id<<1|1,mid,r));
}
void solve(){
	f_(i,n,1){
		for(auto x : vec[i]){
			if(2*x-i>n) continue ;
			update(2*x-i,n+1,a[i]+a[x]);
		}
		for(auto x : Q[i]){
			ans[x.S]=query(i,x.F+1);
		}
	}
}
void shift(int id,int l,int r){
	int mid=(l+r)>>1;
	maxm(lazy[id<<1],lazy[id]);
	maxm(lazy[id<<1|1],lazy[id]);
	maxm(seg[id<<1],Mx[id<<1]+lazy[id]);
	maxm(seg[id<<1|1],Mx[id<<1|1]+lazy[id]);
}

main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	fill(lazy,lazy+xn,-inf);
	fill(Mx,Mx+xn,-inf);
	cin>>n;
	f(i,1,n+1) cin>>a[i];
	cin>>m;
	f(i,1,m+1){
		int l,r;
		cin>>l>>r;
		Q[l].pb({r,i});
	}
	find();
	build();
	solve();
	f(i,1,m+1) cout<<ans[i]<<" ";
}

Compilation message

jumps.cpp: In function 'void shift(long long int, long long int, long long int)':
jumps.cpp:99:6: warning: unused variable 'mid' [-Wunused-variable]
   99 |  int mid=(l+r)>>1;
      |      ^~~
jumps.cpp: At global scope:
jumps.cpp:106:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  106 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55116 KB Output is correct
2 Correct 23 ms 55128 KB Output is correct
3 Correct 23 ms 55108 KB Output is correct
4 Correct 24 ms 55120 KB Output is correct
5 Correct 23 ms 55120 KB Output is correct
6 Correct 23 ms 55116 KB Output is correct
7 Correct 23 ms 55116 KB Output is correct
8 Correct 24 ms 55184 KB Output is correct
9 Correct 22 ms 55104 KB Output is correct
10 Correct 23 ms 55116 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55116 KB Output is correct
2 Correct 23 ms 55128 KB Output is correct
3 Correct 23 ms 55108 KB Output is correct
4 Correct 24 ms 55120 KB Output is correct
5 Correct 23 ms 55120 KB Output is correct
6 Correct 23 ms 55116 KB Output is correct
7 Correct 23 ms 55116 KB Output is correct
8 Correct 24 ms 55184 KB Output is correct
9 Correct 22 ms 55104 KB Output is correct
10 Correct 23 ms 55116 KB Output is correct
11 Correct 292 ms 82204 KB Output is correct
12 Correct 274 ms 82284 KB Output is correct
13 Correct 270 ms 82400 KB Output is correct
14 Correct 262 ms 82276 KB Output is correct
15 Correct 287 ms 82416 KB Output is correct
16 Correct 266 ms 81704 KB Output is correct
17 Correct 271 ms 80460 KB Output is correct
18 Correct 262 ms 81592 KB Output is correct
19 Correct 287 ms 82040 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 73200 KB Output is correct
2 Correct 96 ms 71868 KB Output is correct
3 Correct 99 ms 71888 KB Output is correct
4 Correct 153 ms 72540 KB Output is correct
5 Correct 146 ms 72852 KB Output is correct
6 Correct 158 ms 72500 KB Output is correct
7 Correct 146 ms 72336 KB Output is correct
8 Correct 141 ms 72368 KB Output is correct
9 Correct 159 ms 72680 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55116 KB Output is correct
2 Correct 23 ms 55128 KB Output is correct
3 Correct 23 ms 55108 KB Output is correct
4 Correct 24 ms 55120 KB Output is correct
5 Correct 23 ms 55120 KB Output is correct
6 Correct 23 ms 55116 KB Output is correct
7 Correct 23 ms 55116 KB Output is correct
8 Correct 24 ms 55184 KB Output is correct
9 Correct 22 ms 55104 KB Output is correct
10 Correct 23 ms 55116 KB Output is correct
11 Correct 292 ms 82204 KB Output is correct
12 Correct 274 ms 82284 KB Output is correct
13 Correct 270 ms 82400 KB Output is correct
14 Correct 262 ms 82276 KB Output is correct
15 Correct 287 ms 82416 KB Output is correct
16 Correct 266 ms 81704 KB Output is correct
17 Correct 271 ms 80460 KB Output is correct
18 Correct 262 ms 81592 KB Output is correct
19 Correct 287 ms 82040 KB Output is correct
20 Correct 165 ms 73200 KB Output is correct
21 Correct 96 ms 71868 KB Output is correct
22 Correct 99 ms 71888 KB Output is correct
23 Correct 153 ms 72540 KB Output is correct
24 Correct 146 ms 72852 KB Output is correct
25 Correct 158 ms 72500 KB Output is correct
26 Correct 146 ms 72336 KB Output is correct
27 Correct 141 ms 72368 KB Output is correct
28 Correct 159 ms 72680 KB Output is correct
29 Correct 970 ms 121668 KB Output is correct
30 Correct 812 ms 118540 KB Output is correct
31 Correct 788 ms 118644 KB Output is correct
32 Correct 1038 ms 121432 KB Output is correct
33 Correct 952 ms 120772 KB Output is correct
34 Correct 923 ms 121932 KB Output is correct
35 Correct 920 ms 121416 KB Output is correct
36 Correct 924 ms 120888 KB Output is correct
37 Correct 900 ms 120400 KB Output is correct
38 Correct 637 ms 121964 KB Output is correct
39 Correct 653 ms 122128 KB Output is correct
40 Correct 624 ms 121404 KB Output is correct
41 Correct 609 ms 121072 KB Output is correct
42 Correct 641 ms 121044 KB Output is correct
43 Correct 633 ms 120988 KB Output is correct
44 Correct 691 ms 121132 KB Output is correct
45 Correct 664 ms 121124 KB Output is correct
46 Correct 663 ms 120184 KB Output is correct
47 Correct 733 ms 120112 KB Output is correct
48 Correct 730 ms 119720 KB Output is correct
49 Correct 664 ms 120260 KB Output is correct
50 Correct 743 ms 119580 KB Output is correct
51 Correct 745 ms 119284 KB Output is correct
52 Correct 862 ms 118632 KB Output is correct
53 Correct 789 ms 118428 KB Output is correct
54 Correct 745 ms 118376 KB Output is correct
55 Correct 757 ms 119048 KB Output is correct