oj.uz

답안 #531042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
531042 2022-02-27T13:17:23 Z AdamGS 밀림 점프 (APIO21_jumps) C++17
4 / 100
 1271 ms 67008 KB 
#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, INF=1e9+7, LG=20;
int T[LIM], lewo[LIM][LG], prawo[LIM][LG], ile[LIM][LG], ma[LIM][LG], n;
void init(int N, vector<int>H) {
	n=N;
	rep(i, n) T[i+1]=H[i];
	stack<pair<int,int>>S;
	T[0]=T[n+1]=INF;
	rep(i, n+2) {
		while(!S.empty() && S.top().st<T[i]) S.pop();
		if(!S.empty()) lewo[i][0]=S.top().nd;
		else lewo[i][0]=i;
		S.push({T[i], i});
	}
	while(!S.empty()) S.pop();
	for(int i=n+1; i>=0; --i) {
		while(!S.empty() && S.top().st<T[i]) S.pop();
		if(!S.empty()) prawo[i][0]=S.top().nd;
		else prawo[i][0]=i;
		S.push({T[i], i});
	}
	for(int j=1; j<LG; ++j) rep(i, n+2) {
		lewo[i][j]=lewo[lewo[i][j-1]][j-1];
		prawo[i][j]=prawo[prawo[i][j-1]][j-1];
	}
	rep(i, n+2) {
		int p=i;
		ile[i][0]=-1;
		for(int j=LG-1; j>=0; --j) if(prawo[p][j]<prawo[lewo[i][0]][0]) {
			p=prawo[p][j];
			ile[i][0]+=1<<j;
		}
		if(ile[i][0]>0) ma[i][0]=ile[i][0];
	}
	for(int j=1; j<LG; ++j) rep(i, n+2) {
		ile[i][j]=ile[i][j-1]+ile[lewo[i][j-1]][j-1];
		ma[i][j]=max(ma[i][j-1], ile[i][j-1]+ma[lewo[i][j-1]][j-1]);
	}
}
int minimum_jumps(int a, int b, int l, int r) {
	++a; ++b; ++l; ++r;
	int p=b;
	for(int i=LG-1; i>=0; --i) if(prawo[p][i]<=r) p=prawo[p][i];
	if(p<l) return -1;
	int x=b;
	for(int i=LG-1; i>=0; --i) if(T[lewo[x][i]]<T[p] && lewo[x][i]>=a) x=lewo[x][i];
	int sum=1, y=x;
	for(int i=LG-1; i>=0; --i) if(prawo[y][i]<l) {
		y=prawo[y][i];
		sum+=1<<i;
	}
	int z=T[y], ans=0, akt=0, ans2=0;
	y=prawo[y][0];
	p=x;
	for(int i=LG-1; i>=0; --i) if(T[lewo[x][i]]<T[y]) {
		ans=max(ans, akt+ma[x][i]);
		akt+=ile[x][i];
		x=lewo[x][i];
	}
	ans=sum-ans;
	for(int i=LG-1; i>=0; --i) if(T[lewo[p][i]]<z) {
		p=lewo[p][i];
		ans2+=1<<i;
	}
	p=lewo[p][0];
	if(prawo[p][0]<=r) ans=min(ans, ans2+2);
	return ans;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 230 ms 53312 KB Output is correct
4 Correct 1271 ms 66968 KB Output is correct
5 Correct 1064 ms 33832 KB Output is correct
6 Correct 989 ms 66908 KB Output is correct
7 Correct 935 ms 45808 KB Output is correct
8 Correct 1250 ms 67008 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 122 ms 52480 KB Output is correct
6 Correct 160 ms 65180 KB Output is correct
7 Correct 77 ms 33552 KB Output is correct
8 Correct 164 ms 65196 KB Output is correct
9 Correct 15 ms 10084 KB Output is correct
10 Correct 168 ms 65216 KB Output is correct
11 Correct 162 ms 66836 KB Output is correct
12 Correct 169 ms 66320 KB Output is correct
13 Correct 153 ms 66516 KB Output is correct
14 Correct 150 ms 65244 KB Output is correct
15 Incorrect 165 ms 65780 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 230 ms 53312 KB Output is correct
4 Correct 1271 ms 66968 KB Output is correct
5 Correct 1064 ms 33832 KB Output is correct
6 Correct 989 ms 66908 KB Output is correct
7 Correct 935 ms 45808 KB Output is correct
8 Correct 1250 ms 67008 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 200 KB Output is correct
12 Correct 0 ms 328 KB Output is correct
13 Correct 2 ms 328 KB Output is correct
14 Correct 3 ms 328 KB Output is correct
15 Correct 2 ms 328 KB Output is correct
16 Incorrect 3 ms 328 KB Output isn't correct
17 Halted 0 ms 0 KB -