oj.uz

Submission #428749

# Submission time Handle Problem Language Result Execution time Memory
428749 2021-06-15T14:12:28 Z hhhhaura Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 15208 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;
	rep(i, A, B) if(h[i] < h[to]) {
		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 1 ms 200 KB Output is correct
3 Correct 3321 ms 12040 KB Output is correct
4 Execution timed out 4034 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 1 ms 200 KB Output is correct
5 Incorrect 3 ms 200 KB Output isn't correct
6 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 1 ms 200 KB Output is correct
5 Incorrect 3 ms 200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 1 ms 200 KB Output is correct
5 Correct 194 ms 12228 KB Output is correct
6 Correct 243 ms 15048 KB Output is correct
7 Correct 88 ms 7828 KB Output is correct
8 Correct 257 ms 15208 KB Output is correct
9 Correct 23 ms 2496 KB Output is correct
10 Correct 294 ms 15168 KB Output is correct
11 Correct 110 ms 15168 KB Output is correct
12 Correct 119 ms 15040 KB Output is correct
13 Correct 111 ms 15040 KB Output is correct
14 Correct 199 ms 15124 KB Output is correct
15 Execution timed out 4006 ms 15060 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 271 ms 7176 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 271 ms 7176 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 1 ms 200 KB Output is correct
3 Correct 3321 ms 12040 KB Output is correct
4 Execution timed out 4034 ms 15124 KB Time limit exceeded
5 Halted 0 ms 0 KB -