Submission #887787

#	Time	Username	Problem	Language	Result	Execution time	Memory
887787		vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	Compilation error	0 ms	0 KiB

jumps

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

const int mxn = 2e5+23, lg = 23;
int l[mxn][lg], r[mxn][lg], jmp1[mxn][lg], jmp2[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++)
	{
		if(h[l[i][0]] > h[r[i][0]])
		{
			jmp1[i][0] = l[i][0];
			jmp2[i][0] = r[i][0];
		}
		else
		{
			jmp2[i][0] = l[i][0];
			jmp1[i][0] = r[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];
			jmp1[v][i] = jmp1[jmp1[v][i-1]][i-1];
			jmp2[v][i] = jmp2[jmp2[v][i-1]][i-1];
		}
	}
}

int minimum_jump(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[v][l[v][0]] <= d)
   	 	{
      		return 1;
    	}
	}
	else
	{
    	for(int i = lg-1; i >= 0; i--)
    	{
      		if(h[jmp1[v][i]] <= h[m])
      		{
	       		cnt |= (1 << i);
	       		v = jmp1[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;
  	}
}

int main()
{
	int n, q;
	cin >> n >> q;
	vector<int> vc;
	for(int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		vc.push_back(x);
	}
	init(n, vc);
	while(q--)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		cout << minimum_jump(a, b, c, d) << '\n';
	}
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccEUdKZ8.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccWTiaLa.o:jumps.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccEUdKZ8.o: in function `main':
stub.cpp:(.text.startup+0x1d1): undefined reference to `minimum_jumps(int, int, int, int)'
collect2: error: ld returned 1 exit status