oj.uz

Submission #428761

# Submission time Handle Problem Language Result Execution time Memory
428761 2021-06-15T14:16:42 Z hhhhaura Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 15284 KB 
#define wiwihorz
#include "jumps.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()

#define MOD 1000000007
#define eps (1e-9)
#define INF 1000000000
using namespace std;

#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
void kout() {cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
int n;
vector<int> L, R, d, h;

void init(int N, vector<int> H) {
	n = N, h = H;
	set<int> s; vector<int> a(n, 0);
	L.assign(n, -1);
	R.assign(n, -1);
	d.assign(n, 0);
	
	rep(i, 0, n - 1) a[i] = i;
	sort(all(a), [](int x, int y) { return h[x] > h[y]; });
	for(auto i : a) {
		auto it = s.lower_bound(i);
		if(it != s.end()) {
			d[i] = d[*it] + 1;
			R[i] = *it; 	
		}
		if(it != s.begin()) {
			it = prev(it);
			L[i] = *it;
		}
		s.insert(i);
	}
//	vprint(all(L));
//	vprint(all(R));
//	vprint(all(d));
	return;
}
/*
7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2 
*/
int minimum_jumps(int A, int B, int C, int D) {
	int to = C, from = -1;
	rep(i, C, D) if(h[i] > h[to]) to = i;
	rrep(i, A, B) {
		if(h[i] > h[to]) break;
		if(from == -1 || h[from] < h[i]) from = i;
	}
	if(from == -1) return -1;
	rep(i, from, to) if(h[i] > h[to]) return -1;
	int cnt = 0, cur = 0, id = from, ans = INF;
	while(id != -1) {
		if(h[id] > h[to]) break;
		cur = id; 
		while(cur < C) cur = R[cur];
		ans = min(ans, cnt + d[id] - d[cur]);
		cnt ++, id = L[id];
	}
	return ans;
}

Compilation message

jumps.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
jumps.cpp:23:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
      |             ^~~~
jumps.cpp:23:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
      |                     ^~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 3350 ms 12112 KB Output is correct
4 Execution timed out 4078 ms 15124 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.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 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 3 ms 200 KB Output is correct
6 Correct 4 ms 200 KB Output is correct
7 Correct 3 ms 200 KB Output is correct
8 Incorrect 5 ms 200 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 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 200 KB Output is correct
5 Correct 3 ms 200 KB Output is correct
6 Correct 4 ms 200 KB Output is correct
7 Correct 3 ms 200 KB Output is correct
8 Incorrect 5 ms 200 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 2 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 191 ms 12168 KB Output is correct
6 Correct 303 ms 15064 KB Output is correct
7 Correct 89 ms 7860 KB Output is correct
8 Correct 243 ms 15148 KB Output is correct
9 Correct 24 ms 2496 KB Output is correct
10 Correct 234 ms 15284 KB Output is correct
11 Correct 124 ms 15112 KB Output is correct
12 Correct 133 ms 15128 KB Output is correct
13 Correct 116 ms 15148 KB Output is correct
14 Correct 261 ms 15140 KB Output is correct
15 Execution timed out 4089 ms 15156 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 1 ms 200 KB Output is correct
4 Incorrect 322 ms 7056 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.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 1 ms 200 KB Output is correct
4 Incorrect 322 ms 7056 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 3350 ms 12112 KB Output is correct
4 Execution timed out 4078 ms 15124 KB Time limit exceeded
5 Halted 0 ms 0 KB -