Submission #740918

#	Time	Username	Problem	Language	Result	Execution time	Memory
740918		tegid	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	1565 ms	80388 KiB

jumps

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

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int arr[200005];

struct node{
	int s,e,m,v;
	vector<int> dec,inc;
	node *l,*r;
	node(int S,int E){
		s=S;e=E;m=(s+e)/2;
		if(s==e){
			v=arr[s];
			dec.pb(arr[s]);
			inc.pb(arr[s]);
		}else{
			l=new node(s,m);
			r=new node(m+1,e);
			v=max(l->v,r->v);
			dec=l->dec;
			while(!dec.empty()&&dec.back()<r->dec[0])dec.pop_back();
			for(int i:(r->dec))dec.pb(i);
			inc=r->inc;
			while(!inc.empty()&&inc.back()<l->inc[0])inc.pop_back();
			for(int i:(l->inc))inc.pb(i);
		}
	}
	int rmaxq(int x,int y){
		if(x>y)return -1;
		if(s>=x&&e<=y)return v;
		if(y<=m)return l->rmaxq(x,y);
		if(x>m)return r->rmaxq(x,y);
		return max(l->rmaxq(x,y),r->rmaxq(x,y));
	}
	int sminq(int x,int y){
		if(s>=x&&e<=y)return dec.back();
		if(y<=m)return l->sminq(x,y);
		return r->sminq(x,y);
	}
	int sdecq(int x,int y,int val){ // largest value in the dec array that is <val
		if(s>=x&&e<=y)return *(--lower_bound(dec.rbegin(),dec.rend(),val));
		if(y<=m)return l->sdecq(x,y,val);
		if(x>m)return r->sdecq(x,y,val);
		
		int lres=l->sdecq(x,y,val),rmax=r->rmaxq(x,y);
		if(lres>rmax)return lres;
		return r->sdecq(x,y,val);
	}
	ii sincq(int x,int y,int val){ // number of elements in the inc array that are >val
		if(s>=x&&e<=y){
			auto it=(upper_bound(inc.rbegin(),inc.rend(),val));
			//printf("%d %d %d %d: it %d\n",x,y,s,e,*it);
			return mp(inc.rend()-it,*it);
		}
		//printf("%d %d\n",s,e);
		if(y<=m)return l->sincq(x,y,val);
		if(x>m)return r->sincq(x,y,val);
		
		ii lres=l->sincq(x,y,val);
		int lmax=l->rmaxq(x,y);
		lres.fi+=r->sincq(x,y,lmax).fi;
		return lres;
	}
}*root;

void init(int N, vector<int> H) {
	for(int i=0;i<N;i++)arr[i]=H[i];
	root=new node(0,N-1);
}

int minimum_jumps(int A, int B, int C, int D) {
	int midmax=root->rmaxq(B+1,C-1),emax=root->rmaxq(C,D);
	if(midmax>emax)return -1;
	
	int smin=root->sminq(A,B);
	if(smin>emax)return -1;
	
	int start=root->sdecq(A,B,emax);
	if(start>midmax)return 1;
	//printf("start %d %d %d\n",start,B+1,C-1);
	
	return 1+root->sincq(B+1,C-1,start).fi;
}

• 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