oj.uz

Submission #428944

# Submission time Handle Problem Language Result Execution time Memory
428944 2021-06-15T15:40:58 Z hhhhaura Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 78972 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, lg;
vector<int> L, R, h;
vector<vector<int>> l, r;
vector<vector<pii>> sp;
int query(int L, int R) {
	if(L > R) return -1;
	int cur = 31 - __builtin_clz(R - L + 1);
	print(L, R, cur);
	pii ans = max(sp[cur][L], sp[cur][R - (1 << cur) + 1]);
	return ans.second;
}
void init(int N, vector<int> H) {
	n = N, lg = 32 - __builtin_clz(n);
	set<int> s; vector<int> a(n, 0);
	L.assign(n + 2, 0);
	R.assign(n + 2, 0);
	h.assign(n + 2, 0);
	h[0] = h[n + 1] = INF;
	rep(i, 0, n - 1) h[i + 1] = H[i];
	rep(i, 1, n) a[i - 1] = i;
	sort(all(a), [](int x, int y) { return h[x] > h[y]; });
	s.insert(n), s.insert(0);
	for(auto i : a) {
		auto it = s.lower_bound(i);
		int x = *it, y = *prev(it);
		if(h[x] < h[y]) swap(x, y);
		R[i] = x, L[i] = *it;
		s.insert(i);
	}
	
	l.assign(lg + 1, vector<int>(n + 2, 0));
	r.assign(lg + 1, vector<int>(n + 2, 0));
	sp.assign(lg + 1, vector<pii>(n + 2, {0, 0}));
	L[0] = R[0] = 0, L[n + 1] = R[n + 1] = n + 1;
	rep(i, 0, n + 1) {
		sp[0][i] = {h[i], i};
		l[0][i] = L[i];
		r[0][i] = R[i];
	}
	rep(i, 1, lg) rep(j, 0, n + 1) {
		sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
		l[i][j] = l[i - 1][l[i - 1][j]];
		r[i][j] = r[i - 1][r[i - 1][j]];
	}
	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) {
	A ++ ,B ++ , C ++, D ++;	
	int st, ll = A - 1, rr = B + 1;
	int x = query(C, D), ans = 0;
/*	while(rr - ll > 1) {
		int mid = (ll + rr) / 2;
		if(h[x] < h[mid]) ll = mid;
		else rr = mid;
	} 
*/
	rrep(i, A, B) {
		if(h[i] > h[x]) break;
		rr = i; 
	}	
	if(st = query(rr, B), st == -1) return -1;
	if(query(st, D) != x) return -1;
	while(h[R[st]] < h[x] && R[st] < C) {
		ans ++, st = R[st];
	}
	if(R[st] <= D && R[st] >= C) return ans + 1;
	while(h[L[st]] < h[x] && L[st] < C) {
		ans ++, st = L[st];
	}
	ans ++, st = L[st];
	if(st <= D && st >= C) return ans;
	else return -1;
/*	rrep(i, 0, lg) {
		int cur = r[i][st];
		if(h[cur] > h[x] || (cur <= D && cur >= C)) continue;
		ans += (1 << i);
		st = r[i][st];
	}
	if(r[0][st] <= D && r[0][st] >= C) return ans + 1;
	rrep(i, 0, lg) {
		int cur = l[i][st];
		if(h[cur] > h[x] || (cur <= D && cur >= C)) continue;
		ans += (1 << i);
		st = l[i][st];
	}
	st = l[0][st];
	if(st <= D && st >= C) return ans + 1;
	else return -1;
*/
}

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; }
      |                     ^~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:85:10: warning: unused variable 'll' [-Wunused-variable]
   85 |  int st, ll = A - 1, rr = B + 1;
      |          ^~

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 1937 ms 60692 KB Output is correct
4 Execution timed out 4033 ms 76260 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 Correct 10 ms 300 KB Output is correct
6 Incorrect 12 ms 328 KB Output isn't correct
7 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 Correct 10 ms 300 KB Output is correct
6 Incorrect 12 ms 328 KB Output isn't correct
7 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 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 212 ms 61460 KB Output is correct
6 Correct 274 ms 76208 KB Output is correct
7 Correct 111 ms 37492 KB Output is correct
8 Correct 305 ms 76312 KB Output is correct
9 Correct 30 ms 10284 KB Output is correct
10 Correct 316 ms 76228 KB Output is correct
11 Correct 183 ms 76208 KB Output is correct
12 Correct 172 ms 76212 KB Output is correct
13 Correct 154 ms 76176 KB Output is correct
14 Correct 236 ms 76336 KB Output is correct
15 Incorrect 191 ms 76232 KB Output isn't correct
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 Correct 1134 ms 33768 KB Output is correct
5 Execution timed out 4010 ms 78972 KB Time limit exceeded
6 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 Correct 1134 ms 33768 KB Output is correct
5 Execution timed out 4010 ms 78972 KB Time limit exceeded
6 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 1937 ms 60692 KB Output is correct
4 Execution timed out 4033 ms 76260 KB Time limit exceeded
5 Halted 0 ms 0 KB -