oj.uz

답안 #428925

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428925 2021-06-15T15:29:53 Z hhhhaura 밀림 점프 (APIO21_jumps) C++14
0 / 100
 4000 ms 73124 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);
	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 = 31 - __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] = y;
		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;
	} 
	if(st = query(rr, B), st == -1) return -1;
	if(query(st, D) != x) return -1;
	while(h[R[st]] < h[x] && (R[st] > D || 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] > D || 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; }
      |                     ^~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1432 ms 58148 KB Output is correct
4 Execution timed out 4019 ms 73068 KB Time limit exceeded
5 Halted 0 ms 0 KB -

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 1 ms 200 KB Output is correct
5 Incorrect 4 ms 200 KB Output isn't correct
6 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 1 ms 200 KB Output is correct
5 Incorrect 4 ms 200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.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 1 ms 200 KB Output is correct
5 Correct 249 ms 58928 KB Output is correct
6 Correct 347 ms 73072 KB Output is correct
7 Correct 130 ms 35944 KB Output is correct
8 Correct 403 ms 73068 KB Output is correct
9 Correct 29 ms 9824 KB Output is correct
10 Correct 294 ms 73072 KB Output is correct
11 Correct 179 ms 73124 KB Output is correct
12 Incorrect 199 ms 73040 KB Output isn't correct
13 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 1 ms 200 KB Output is correct
4 Correct 280 ms 32184 KB Output is correct
5 Correct 1623 ms 73108 KB Output is correct
6 Correct 651 ms 11332 KB Output is correct
7 Correct 1642 ms 73072 KB Output is correct
8 Correct 675 ms 24368 KB Output is correct
9 Correct 1306 ms 73116 KB Output is correct
10 Execution timed out 4062 ms 73092 KB Time limit exceeded
11 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 1 ms 200 KB Output is correct
4 Correct 280 ms 32184 KB Output is correct
5 Correct 1623 ms 73108 KB Output is correct
6 Correct 651 ms 11332 KB Output is correct
7 Correct 1642 ms 73072 KB Output is correct
8 Correct 675 ms 24368 KB Output is correct
9 Correct 1306 ms 73116 KB Output is correct
10 Execution timed out 4062 ms 73092 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1432 ms 58148 KB Output is correct
4 Execution timed out 4019 ms 73068 KB Time limit exceeded
5 Halted 0 ms 0 KB -