Submission #418764

#	Time	Username	Problem	Language	Result	Execution time	Memory
418764		MohamedAhmed04	Triple Jump (JOI19_jumps)	C++17	100 / 100	1430 ms	87872 KiB

jumps

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 5e5 + 10 ;

int arr[MAX] ;
int n ;

vector< pair<int , int> >queries[MAX] ;
vector<int>v[MAX] ;

int ans[MAX] ;

struct Node
{
	int x = 0 , y = 0 , val = 0 ;
};

Node tree[4 * MAX] ;

Node Merge(Node &a , Node &b)
{
	Node c ;
	c.x = max(a.x , b.x) ;
	c.y = max(a.y , b.y) ;
	c.val = max({a.val , b.val , a.y + b.x}) ;
	return c ;
}

void build(int node , int l , int r)
{
	if(l == r)
	{
		tree[node].x = arr[l] ;
		tree[node].val = tree[node].x + tree[node].y ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	build(node << 1 , l , mid) ;
	build(node << 1 | 1 , mid+1 , r) ;
	tree[node] = Merge(tree[node << 1] , tree[node << 1 | 1]) ;
}

void update(int node , int l , int r , int idx , int val)
{
	if(idx > r || idx < l)
		return ;
	if(l == r)
	{
		tree[node].y = max(tree[node].y , val) ;
		tree[node].val = tree[node].x + tree[node].y ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(node << 1 , l , mid , idx , val) ;
	update(node << 1 | 1 , mid+1 , r , idx , val) ;
	tree[node] = Merge(tree[node << 1] , tree[node << 1 | 1]) ;
}

Node tmp ;

Node query(int node , int l , int r , int from , int to)
{
	if(from > r || to < l)
		return tmp ;
	if(l >= from && r <= to)
		return tree[node] ;
	int mid = (l + r) >> 1 ;
	Node x = query(node << 1 , l , mid , from , to) ;
	Node y = query(node << 1 | 1 , mid+1 , r , from , to) ;
	return Merge(x , y) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	int q ;
	cin>>q ;
	for(int i = 1 ; i <= q ; ++i)
	{
		int l , r ;
		cin>>l>>r ;
		queries[l].emplace_back(r , i) ;
	}
	stack<int>s ;
	for(int i = 1 ; i <= n ; ++i)
	{
		while(s.size() && arr[i] >= arr[s.top()])
			v[s.top()].push_back(i) , s.pop() ;
		if(s.size())
			v[s.top()].push_back(i) ;
		s.push(i) ;
	}
	build(1 , 1 , n) ;
	for(int i = n ; i >= 1 ; --i)
	{
		for(auto &j : v[i])
		{
			if(2*j - i <= n)
				update(1 , 1 , n , 2*j - i , arr[i] + arr[j]) ;
		}
		for(auto &p : queries[i])
			ans[p.second] = query(1 , 1 , n , i+2 , p.first).val ;
	}
	for(int i = 1 ; i <= q ; ++i)
		cout<<ans[i]<<"\n" ;
	return 0 ;
}		

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54