oj.uz

Submission #1041073

# Submission time Handle Problem Language Result Execution time Memory
1041073 2024-08-01T14:56:30 Z underwaterkillerwhale Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 751 ms 84172 KB 
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for (auto id : v)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int INF = 2e9;
const ll BASE = 137;

int n;
int a[N];
int spt[N][25], spt2[N][25];
pair<int,int> mx[N][25];
pair<int,int> nxt[N];

pair<int,int> get (int L, int R) {
    if (L > R) return {-INF, 0};
    int K = 31 - __builtin_clz(R - L + 1);
    return max(mx[L][K], mx[R - (1 << K) + 1][K]);
}

int minimum_jumps (int A, int B, int C, int D)  {
    ++A, ++B, ++C, ++ D;
    int X = get(C, D).fs;
    int bound; {
        int lf = A, rt = B;
        while (lf < rt) {
            int mid = lf + rt >> 1;
            if (get(mid, B).fs < X) rt = mid;
            else lf = mid + 1;
        }
        bound = lf;
    }
    if (get(bound, B).fs > X) {
        return -1;
    }
    if (get(B + 1, C - 1).fs > X) {
        return -1;
    }
    int pos = get(bound, B).se;
    ll res = 0;
    reb (i, 20, 0) {
//        cout << pos<<" "<<spt2[pos][i]<<" "<<get(B + 1, C - 1).fs<<"\n";
        if (a[spt2[pos][i]] <= get(B + 1, C - 1).fs) {
            pos = spt2[pos][i];
            res += (1 << i);
        }
    }
//    cout << res <<"\n";
    ++res;
    pos = spt2[pos][0];
    if (pos < C) ++res;
    return res;
}

//void solution() {
void init (int _n, vector<int> _a) {
//    cin >> n;
//    rep (i, 1, n) cin >> a[i];
    n = _n;
    rep (i, 1, n) a[i] = _a[i - 1];
    stack<pair<int,int>> st;
    rep (i, 1, n) {
        while (!st.empty() && st.top().se < a[i]) st.pop();
        if (st.empty()) nxt[i].fs = i;
        else nxt[i].fs = st.top().fs;
        st.push({i, a[i]});
    }
    stack<pair<int,int>> ().swap(st);
    reb (i, n, 1) {
        while (!st.empty() && st.top().se < a[i]) st.pop();
        if (st.empty()) nxt[i].se = i;
        else nxt[i].se = st.top().fs;
        st.push({i, a[i]});
    }
    rep (i, 1, n) {
        if (a[nxt[i].fs] > a[nxt[i].se]) swap (nxt[i].fs, nxt[i].se);
        spt[i][0] = nxt[i].fs;
        spt2[i][0] = nxt[i].se;
    }
    rep (j, 1, 20)
    rep (i, 1, n) spt[i][j] = spt[spt[i][j - 1]][j - 1], spt2[i][j] = spt2[spt2[i][j - 1]][j - 1];
    rep (i, 1, n) mx[i][0] = {a[i], i};
    for (int j = 1; (1 << j) <= n; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
//    cout << minimum_jumps(4, 4, 6, 6);
}

//#define file (name) freopen(name".inp","r",stdin); \
//freopen(name".out","w",stdout);
//int main () {
////    file("c");
//    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int num_Test = 1;
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
no bug challenge +2
7
3 2 1 6 4 5 7
*/

Compilation message

jumps.cpp:102:1: warning: multi-line comment [-Wcomment]
  102 | //#define file (name) freopen(name".inp","r",stdin); \
      | ^
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:41:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |             int mid = lf + rt >> 1;
      |                       ~~~^~~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:98:97: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   98 |         for (int i = 1; i + (1 << j) - 1 <= n; ++i) mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
      |                                                                                               ~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 108 ms 73136 KB Output is correct
4 Correct 751 ms 84172 KB Output is correct
5 Correct 589 ms 51492 KB Output is correct
6 Correct 728 ms 84048 KB Output is correct
7 Correct 549 ms 64336 KB Output is correct
8 Correct 724 ms 84048 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Incorrect 1 ms 8536 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 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Incorrect 1 ms 8536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 42 ms 73808 KB Output is correct
6 Correct 53 ms 82524 KB Output is correct
7 Correct 24 ms 50520 KB Output is correct
8 Correct 54 ms 82552 KB Output is correct
9 Correct 7 ms 21336 KB Output is correct
10 Incorrect 54 ms 82612 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8636 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Incorrect 138 ms 46424 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 8536 KB Output is correct
2 Correct 1 ms 8636 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Incorrect 138 ms 46424 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 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 108 ms 73136 KB Output is correct
4 Correct 751 ms 84172 KB Output is correct
5 Correct 589 ms 51492 KB Output is correct
6 Correct 728 ms 84048 KB Output is correct
7 Correct 549 ms 64336 KB Output is correct
8 Correct 724 ms 84048 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 ms 8536 KB Output is correct
11 Correct 1 ms 8536 KB Output is correct
12 Correct 1 ms 8536 KB Output is correct
13 Incorrect 1 ms 8536 KB Output isn't correct
14 Halted 0 ms 0 KB -