oj.uz

Submission #531049

# Submission time Handle Problem Language Result Execution time Memory
531049 2022-02-27T14:03:06 Z AdamGS Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1223 ms 66876 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 235 ms 53240 KB Output is correct
4 Correct 1223 ms 66780 KB Output is correct
5 Correct 945 ms 33856 KB Output is correct
6 Correct 1153 ms 66848 KB Output is correct
7 Correct 924 ms 45892 KB Output is correct
8 Correct 1186 ms 66876 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 2 ms 200 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 2 ms 200 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 127 ms 52564 KB Output is correct
6 Correct 166 ms 65180 KB Output is correct
7 Correct 81 ms 33472 KB Output is correct
8 Correct 153 ms 65168 KB Output is correct
9 Correct 15 ms 10056 KB Output is correct
10 Correct 158 ms 65308 KB Output is correct
11 Correct 197 ms 66860 KB Output is correct
12 Correct 153 ms 66212 KB Output is correct
13 Correct 169 ms 66344 KB Output is correct
14 Correct 167 ms 65216 KB Output is correct
15 Incorrect 157 ms 65904 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory 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 Incorrect 205 ms 30088 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory 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 Incorrect 205 ms 30088 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 235 ms 53240 KB Output is correct
4 Correct 1223 ms 66780 KB Output is correct
5 Correct 945 ms 33856 KB Output is correct
6 Correct 1153 ms 66848 KB Output is correct
7 Correct 924 ms 45892 KB Output is correct
8 Correct 1186 ms 66876 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 0 ms 328 KB Output is correct
11 Correct 0 ms 200 KB Output is correct
12 Correct 0 ms 200 KB Output is correct
13 Correct 2 ms 200 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 -