Submission #887797

#	Time	Username	Problem	Language	Result	Execution time	Memory
887797		vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	748 ms	58448 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;

const int mxn = 2e5+23, lg = 23;
int l[mxn][lg], r[mxn][lg], jmp[mxn][lg];
int n;
vector<int> h;

void init(int nn, vector<int> hh)
{
	n = nn;
	h = hh;
	h.insert(h.begin(), 1e9);
	h.push_back(1e9);
	stack<pair<int, int>> s;
	n = h.size();
	for(int i = 0; i < n; i++)
	{
		while(s.size() && (s.top().first < h[i]))
		{
			s.pop();
		}
		if(s.size())
		{
			l[i][0] = s.top().second;
		}
		else
		{
			l[i][0] = i;
		}
		s.push({h[i], i});
	}
	while(s.size())
	{
		s.pop();
	}
	for(int i = n-1; i >= 0; i--)
	{
		while(s.size() && (s.top().first < h[i]))
		{
			s.pop();
		}
		if(s.size())
		{
			r[i][0] = s.top().second;
		}
		else
		{
			r[i][0] = i;
		}
		s.push({h[i], i});
	}

	for(int i = 0; i <= n; i++)
	{
		jmp[i][0] = r[i][0];
		if(h[l[i][0]] > h[r[i][0]])
		{
			jmp[i][0] = l[i][0];
		}
	}

	for(int i = 1; i < lg; i++)
	{
		for(int v = 0; v <= n; v++)
		{
			l[v][i] = l[l[v][i-1]][i-1];
			r[v][i] = r[r[v][i-1]][i-1];
			jmp[v][i] = jmp[jmp[v][i-1]][i-1];
		}
	}
}

int minimum_jumps(int a, int b, int c, int d)
{
	a++;
	b++;
	c++;
	d++;
	if((c-b) == 1)
	{
		if(r[b][0] > d)
		{
			return -1;
		}
		else
		{
			return 1;
		}
 	}
 	int m = b+1;
  	for(int i = lg-1; i >= 0; i--)
  	{
    	if(r[m][i] < c)
    	{
      		m = r[m][i];
    	}
 	}
	if(h[b] > h[m])
	{
		if(r[b][0] > d)
		{
			return -1;
		}
		else
		{
			return 1;
		}
  	}
  	int v = b;
  	for(int i = lg-1; i >= 0; i--) // best start
  	{
   		if((a <= l[v][i]) && (h[l[v][i]] < h[m]))
   		{
      		v = l[v][i];
   		}
 	}
  	int cnt = 0;
 	if(a <= l[v][0])
 	{
   	 	if(r[l[v][0]][0] <= d)
   	 	{
      		return 1;
    	}
	}
	else
	{
    	for(int i = lg-1; i >= 0; i--)
    	{
      		if(h[jmp[v][i]] <= h[m])
      		{
	       		cnt |= (1 << i);
	       		v = jmp[i][v];
     		}
    	}
	    if(v == m)
	    {
	    	if(r[v][0] > d)
	    	{
	    		return -1;
	    	}
	    	else
	    	{
	    		return ++cnt;
	    	}
	    }
	    if((0 < l[v][0]) && (r[l[v][0]][0] <= d))
	    {
	      	return cnt+2;
	    }
 	}
  	for(int i = lg-1; i >= 0; i--)
  	{
    	if(r[v][i] < c)
    	{
      		cnt += (1<<i);
      		v = r[v][i];
    	}
  	}
  	if((r[v][0] < c) || (r[v][0] > d))
  	{
  		return -1;
  	}
  	else
  	{
  		return ++cnt;
  	}
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19