oj.uz

Submission #418558

# Submission time Handle Problem Language Result Execution time Memory
418558 2021-06-05T13:49:54 Z MohamedAhmed04 Triple Jump (JOI19_jumps) C++14
0 / 100
 81 ms 5192 KB 
#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(20 , 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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 204 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 3 ms 328 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 4 ms 320 KB Output is correct
7 Incorrect 4 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 204 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 3 ms 328 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 4 ms 320 KB Output is correct
7 Incorrect 4 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 5164 KB Output is correct
2 Correct 74 ms 5132 KB Output is correct
3 Correct 76 ms 5132 KB Output is correct
4 Correct 81 ms 5092 KB Output is correct
5 Correct 81 ms 5112 KB Output is correct
6 Incorrect 73 ms 5192 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 204 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 3 ms 328 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 4 ms 320 KB Output is correct
7 Incorrect 4 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -