oj.uz

답안 #424033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
424033 2021-06-11T15:38:58 Z SorahISA 밀림 점프 (APIO21_jumps) C++17
23 / 100
 1391 ms 44176 KB 
#include "jumps.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int getRand(int L, int R) {
    if (L > R) swap(L, R);
    return (int)(rng() % (uint64_t)(R - L + 1) + L);
}

const int INF = 1E9;
const int maxn = 1 << 18;
const int lgmx = 18;
// const int maxn = 1 << 4;
// const int lgmx = 4;

int N, sparse[lgmx][maxn];
pii jump[lgmx][maxn]; /// (jump lo_edge, jump hi_edge)
vector<int> H;

inline int chmin(int &x, int y) {return x <= y ? 0 : x = y, 1;}

inline int QueryMax(int L, int R) {
    int lay = __lg(R - L + 1);
    return max(sparse[lay][L], sparse[lay][R - (1<<lay) + 1]);
}

void init(int _N, vector<int> _H) {
    N = _N + 2;
    H.eb(N + 1); for (auto x : _H) H.eb(x); H.eb(N + 2);
    
    for (int i = 0; i < N; ++i) sparse[0][i] = H[i];
    
    for (int lay = 1; lay < lgmx; ++lay) {
        for (int i = 0; i < N-(1<<lay)+1; ++i) {
            sparse[lay][i] = max(sparse[lay-1][i], sparse[lay-1][i+(1<<lay-1)]);
        }
    }
    
    jump[0][0] = {0, N-1}, jump[0][N-1] = {N-1, N-1};
    
    for (int i = 1, lo, mi, hi; i < N-1; ++i) {
        auto &jmp = jump[0][i];
        
        lo = 0, hi = i;
        while (lo < hi) {
            mi = lo + hi + 1 >> 1;
            QueryMax(mi, i) > H[i] ? lo = mi : hi = mi - 1;
        }
        jmp.X = lo;
        
        lo = i, hi = N-1;
        while (lo < hi) {
            mi = lo + hi >> 1;
            QueryMax(i, mi) > H[i] ? hi = mi : lo = mi + 1;
        }
        jmp.Y = lo;
        
        if (H[jmp.X] > H[jmp.Y]) swap(jmp.X, jmp.Y);
    }
    
    for (int lay = 1; lay < lgmx; ++lay) {
        for (int i = 0; i < N; ++i) {
            auto anc = jump[lay-1][i];
            jump[lay][i].X = jump[lay-1][anc.X].X;
            jump[lay][i].Y = jump[lay-1][anc.Y].Y;
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    ++A, ++B, ++C, ++D;
    if (QueryMax(B, C) != H[C]) return -1;
    
    int lo = A, hi = B, mi;
    while (lo < hi) {
        mi = lo + hi >> 1;
        if (QueryMax(mi, B) > H[C]) lo = mi + 1;
        else hi = mi;
    }
    A = B = lo;
    
    int ans = 0;
    for (int i = lgmx-1; i >= 0; --i) {
        if (H[jump[i][A].Y] <= H[C]) A = jump[i][A].Y, ans += 1 << i;
    }
    for (int i = lgmx-1; i >= 0; --i) {
        if (H[jump[i][A].X] <= H[C]) A = jump[i][A].X, ans += 1 << i;
    }
    return ans;
}

Compilation message

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:50:75: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   50 |             sparse[lay][i] = max(sparse[lay-1][i], sparse[lay-1][i+(1<<lay-1)]);
      |                                                                        ~~~^~
jumps.cpp:61:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |             mi = lo + hi + 1 >> 1;
      |                  ~~~~~~~~^~~
jumps.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |             mi = lo + hi >> 1;
      |                  ~~~^~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:91:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         mi = lo + hi >> 1;
      |              ~~~^~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 420 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Incorrect 215 ms 34996 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 281 ms 20092 KB Output is correct
5 Correct 1041 ms 44068 KB Output is correct
6 Correct 705 ms 7416 KB Output is correct
7 Correct 1109 ms 44064 KB Output is correct
8 Correct 526 ms 15160 KB Output is correct
9 Correct 1112 ms 44052 KB Output is correct
10 Correct 1387 ms 44104 KB Output is correct
11 Correct 1380 ms 44084 KB Output is correct
12 Correct 1391 ms 44036 KB Output is correct
13 Correct 1147 ms 44068 KB Output is correct
14 Correct 1179 ms 44084 KB Output is correct
15 Correct 1083 ms 44052 KB Output is correct
16 Correct 1163 ms 44104 KB Output is correct
17 Correct 1 ms 456 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 1 ms 456 KB Output is correct
20 Correct 2 ms 456 KB Output is correct
21 Correct 3 ms 456 KB Output is correct
22 Correct 3 ms 456 KB Output is correct
23 Correct 3 ms 456 KB Output is correct
24 Correct 2 ms 456 KB Output is correct
25 Correct 1 ms 456 KB Output is correct
26 Correct 1 ms 584 KB Output is correct
27 Correct 13 ms 840 KB Output is correct
28 Correct 23 ms 840 KB Output is correct
29 Correct 28 ms 840 KB Output is correct
30 Correct 23 ms 840 KB Output is correct
31 Correct 14 ms 840 KB Output is correct
32 Correct 1 ms 328 KB Output is correct
33 Correct 51 ms 25448 KB Output is correct
34 Correct 93 ms 44036 KB Output is correct
35 Correct 82 ms 44052 KB Output is correct
36 Correct 90 ms 44084 KB Output is correct
37 Correct 107 ms 44052 KB Output is correct
38 Correct 82 ms 44084 KB Output is correct

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 281 ms 20092 KB Output is correct
5 Correct 1041 ms 44068 KB Output is correct
6 Correct 705 ms 7416 KB Output is correct
7 Correct 1109 ms 44064 KB Output is correct
8 Correct 526 ms 15160 KB Output is correct
9 Correct 1112 ms 44052 KB Output is correct
10 Correct 1387 ms 44104 KB Output is correct
11 Correct 1380 ms 44084 KB Output is correct
12 Correct 1391 ms 44036 KB Output is correct
13 Correct 1147 ms 44068 KB Output is correct
14 Correct 1179 ms 44084 KB Output is correct
15 Correct 1083 ms 44052 KB Output is correct
16 Correct 1163 ms 44104 KB Output is correct
17 Correct 1 ms 456 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 1 ms 456 KB Output is correct
20 Correct 2 ms 456 KB Output is correct
21 Correct 3 ms 456 KB Output is correct
22 Correct 3 ms 456 KB Output is correct
23 Correct 3 ms 456 KB Output is correct
24 Correct 2 ms 456 KB Output is correct
25 Correct 1 ms 456 KB Output is correct
26 Correct 1 ms 584 KB Output is correct
27 Correct 13 ms 840 KB Output is correct
28 Correct 23 ms 840 KB Output is correct
29 Correct 28 ms 840 KB Output is correct
30 Correct 23 ms 840 KB Output is correct
31 Correct 14 ms 840 KB Output is correct
32 Correct 1 ms 328 KB Output is correct
33 Correct 51 ms 25448 KB Output is correct
34 Correct 93 ms 44036 KB Output is correct
35 Correct 82 ms 44052 KB Output is correct
36 Correct 90 ms 44084 KB Output is correct
37 Correct 107 ms 44052 KB Output is correct
38 Correct 82 ms 44084 KB Output is correct
39 Correct 1 ms 456 KB Output is correct
40 Correct 0 ms 456 KB Output is correct
41 Correct 1 ms 456 KB Output is correct
42 Correct 206 ms 20096 KB Output is correct
43 Correct 1180 ms 44068 KB Output is correct
44 Correct 775 ms 7484 KB Output is correct
45 Correct 1068 ms 44048 KB Output is correct
46 Correct 761 ms 15152 KB Output is correct
47 Correct 1046 ms 44000 KB Output is correct
48 Correct 1384 ms 44120 KB Output is correct
49 Correct 1329 ms 44076 KB Output is correct
50 Correct 1391 ms 44052 KB Output is correct
51 Correct 1230 ms 44052 KB Output is correct
52 Correct 1197 ms 44076 KB Output is correct
53 Correct 1089 ms 44164 KB Output is correct
54 Correct 1097 ms 44176 KB Output is correct
55 Correct 1 ms 328 KB Output is correct
56 Incorrect 164 ms 43928 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 420 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Incorrect 215 ms 34996 KB Output isn't correct
4 Halted 0 ms 0 KB -