oj.uz

답안 #428927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428927 2021-06-15T15:31:26 Z hhhhaura 밀림 점프 (APIO21_jumps) C++14
0 / 100
 4000 ms 73220 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] = *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;
	} 
	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 1246 ms 58260 KB Output is correct
4 Execution timed out 4010 ms 73120 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 3 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 3 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 200 ms 58876 KB Output is correct
6 Correct 262 ms 73136 KB Output is correct
7 Correct 112 ms 35972 KB Output is correct
8 Correct 299 ms 73088 KB Output is correct
9 Correct 26 ms 9792 KB Output is correct
10 Correct 295 ms 73076 KB Output is correct
11 Correct 156 ms 73092 KB Output is correct
12 Incorrect 149 ms 73072 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 392 ms 32212 KB Output is correct
5 Correct 1413 ms 73108 KB Output is correct
6 Correct 833 ms 11320 KB Output is correct
7 Correct 1250 ms 73096 KB Output is correct
8 Correct 522 ms 24240 KB Output is correct
9 Correct 1238 ms 73112 KB Output is correct
10 Execution timed out 4080 ms 73220 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 392 ms 32212 KB Output is correct
5 Correct 1413 ms 73108 KB Output is correct
6 Correct 833 ms 11320 KB Output is correct
7 Correct 1250 ms 73096 KB Output is correct
8 Correct 522 ms 24240 KB Output is correct
9 Correct 1238 ms 73112 KB Output is correct
10 Execution timed out 4080 ms 73220 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 1246 ms 58260 KB Output is correct
4 Execution timed out 4010 ms 73120 KB Time limit exceeded
5 Halted 0 ms 0 KB -