Submission #418557

#	Time	Username	Problem	Language	Result	Execution time	Memory
418557		MohamedAhmed04	Triple Jump (JOI19_jumps)	C++14	5 / 100	4038 ms	6976 KiB

jumps

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 5e5 + 10 ;

int arr[MAX] ;

int n ;
pair<int , int> tree[4 * MAX] ;

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

pair<int , int>query(int node , int l , int r , int from , int to)
{
	if(from > r || to < l)
		return {-1 , -1} ;
	if(l >= from && r <= to)
		return tree[node] ;
	int mid = (l + r) >> 1 ;
	pair<int , int>a = query(node << 1 , l , mid , from , to) ;
	pair<int , int>b = query(node << 1 | 1 , mid+1 , r , from , to) ;
	return max(a , b) ;
}

vector<int>v ;

int calc(int l , int r) 
{
	v.clear() ;
	for(int i = 0 ; i < min(50 , r-l+1) ; ++i)
	{
		int idx = query(1 , 1 , n , l , r).second ;
		v.push_back(idx) ;
		update(1 , 1 , n , idx , -1) ;
	}
	for(auto &i : v)
		update(1 , 1 , n , i , arr[i]) ;
	sort(v.begin() , v.end()) ;
	int ans = 0 ;
	for(int i = 0 ; i < v.size() ; ++i)
	{
		for(int j = i+1 ; j < v.size() ; ++j)
		{
			int diff = v[j] - v[i] ;
			if(v[i] != l)
				ans = max(ans , arr[v[i]] + arr[v[j]] + query(1 , 1 , n , max(l , v[i] - diff) , v[i]-1).first) ;
			if(v[j] + diff <= r)
				ans = max(ans , arr[v[i]] + arr[v[j]] + query(1 , 1 , n , v[j] + diff , r).first) ;
		}
	}
	return ans ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	for(int i = 1 ; i <= n ; ++i)
		update(1 , 1 , n , i , arr[i]) ;
	int q ;
	cin>>q ;
	while(q--)
	{
		int l , r ;
		cin>>l>>r ;
		cout<<calc(l , r)<<"\n" ;
	}
	return 0 ;
}		

Compilation message (stderr)

jumps.cpp: In function 'int calc(int, int)':
jumps.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0 ; i < v.size() ; ++i)
      |                  ~~^~~~~~~~~~
jumps.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int j = i+1 ; j < v.size() ; ++j)
      |                     ~~^~~~~~~~~~

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