oj.uz

답안 #740918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
740918 2023-05-13T09:18:45 Z tegid 밀림 점프 (APIO21_jumps) C++17
4 / 100
 1565 ms 80388 KB 
#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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 229 ms 65312 KB Output is correct
4 Correct 1565 ms 80388 KB Output is correct
5 Correct 1028 ms 40944 KB Output is correct
6 Correct 1368 ms 80388 KB Output is correct
7 Correct 1018 ms 55472 KB Output is correct
8 Correct 1549 ms 80372 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Incorrect 2 ms 208 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Incorrect 2 ms 208 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Incorrect 85 ms 52772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 264 ms 30100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 264 ms 30100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 229 ms 65312 KB Output is correct
4 Correct 1565 ms 80388 KB Output is correct
5 Correct 1028 ms 40944 KB Output is correct
6 Correct 1368 ms 80388 KB Output is correct
7 Correct 1018 ms 55472 KB Output is correct
8 Correct 1549 ms 80372 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Incorrect 2 ms 208 KB Output isn't correct
14 Halted 0 ms 0 KB -