oj.uz

Submission #975116

# Submission time Handle Problem Language Result Execution time Memory
975116 2024-05-04T13:12:37 Z yoav_s Rainforest Jumps (APIO21_jumps) C++17
23 / 100
 4000 ms 150596 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e18;
const ll mod = 1e9 + 7;

#include "jumps.h"

v H;
ll N;
v nextHigher;
v prevHigher;
v st;
ll n;
vv largestLifting;
v rightHeight;
ll logN;
v nextLargest;
vv nextLifting;
vv st2;

ll query(ll l, ll r, v &st, bool maxi = true)
{
    ll n = st.size() / 2;
    l += n;
    r += n;
    ll res = maxi? -INF : INF;
    while (l <= r)
    {
        if (l % 2 == 1)
        {
            if (maxi)
                res = max(res, st[l]);
            else
                res = min(res, st[l]);
            l++;
        }
        if (r % 2 == 0)
        {
            if (maxi)
                res = max(res,st[r]);
            else
                res = min(res, st[l]);
            r--;
        }
        l /= 2;
        r /= 2;
    }
    return res;
}

ll largestSmaller(ll l, ll r, ll threshold, vv &st)
{
    ll n = st.size() / 2;
    ll tl = n, tr = threshold + n - 1;
    v segs, segsRev;
    while (tl <= tr)
    {
        if (tl % 2 == 1)
        {
            segs.pb(tl);
            tl++;
        }
        if (tr % 2 == 0)
        {
            segsRev.pb(tr);
            tr--;
        }
        tl /= 2; tr /= 2;
    }
    reverse(all(segs)); for (ll x : segs) segsRev.pb(x);
    for (ll x : segsRev)
    {
        auto ptr = lower_bound(all(st[x]), l);
        if (ptr != st[x].end() && (*ptr) <= r)
        {
            while (x < n)
            {
                auto ptr = lower_bound(all(st[2 * x + 1]), l);
                if (ptr != st[2 * x + 1].end() && (*ptr) <= r) x = 2 * x + 1;
                else x *= 2;
            }
            return st[x][0];
        }
    }
    return -1;
}

void init(int Nn, std::vector<int> Hh) {
    vp hSorted;
    for (ll i =0 ; i < Nn; i++) hSorted.eb(Hh[i], i);
    sort(all(hSorted));
    H = v(Nn, -1);
    for (ll i = 0; i < hSorted.size(); i++) H[hSorted[i].s] = i;
    N = Nn;
    nextHigher = v(N, N);
    stack<p> mon;
    for (ll i = N - 1; i >= 0; i--)
    {
        while (!mon.empty() && mon.top().s <= H[i]) mon.pop();
        if (!mon.empty()) nextHigher[i] = mon.top().f;
        mon.emplace(i, H[i]);
    }
    mon = stack<p>();
    prevHigher = v(N, -1);
    for (ll i = 0; i < N; i++)
    {
        while (!mon.empty() && mon.top().s <= H[i]) mon.pop();
        if (!mon.empty()) prevHigher[i] = mon.top().f;
        mon.emplace(i, H[i]);
    }
    n = pow(2, ceil(log2(N)));
    st = v(2 * n, -INF);
    for (ll i = 0; i < N; i++) st[n + i] = H[i];
    for (ll i = n - 1;  i> 0; i--) st[i] = max(st[2 * i], st[2 * i + 1]);
    nextLargest = v(N, -1);
    for (ll i = 0; i < N; i++)
    {
        if (nextHigher[i] != N) nextLargest[i] = nextHigher[i];
        if (prevHigher[i] != -1 && (nextLargest[i] == -1 || H[nextLargest[i]] < H[prevHigher[i]])) nextLargest[i] = prevHigher[i];
    }
    logN = log2(N);
    largestLifting = vv(N, v(logN + 1, -1));
    for (ll i = 0; i < N; i++) largestLifting[i][0] = nextLargest[i];
    for (ll iter = 1; iter <= logN; iter++)
    {
        for (ll i= 0; i < N; i++)
        {
            if (largestLifting[i][iter - 1] == -1) largestLifting[i][iter] = -1;
            else largestLifting[i][iter] = largestLifting[largestLifting[i][iter - 1]][iter - 1];
        }
    }
    vv nextHigherRev(N + 1);
    for (ll i =0; i <N; i++) nextHigherRev[nextHigher[i]].pb(i);
    rightHeight = v(N + 1, 0);
    stack<p> dfs;
    dfs.emplace(N, 0);
    while (!dfs.empty())
    {
        auto top = dfs.top();
        dfs.pop();
        rightHeight[top.f] = top.s;
        for (ll x : nextHigherRev[top.f]) dfs.emplace(x, top.s + 1);
    }
    st2 = vv(2 * n, v());
    for (ll i = 0; i < N; i++) st2[H[i] + n] = {i};
    for (ll i = n - 1;  i> 0; i--)
    {
        merge(all(st2[2 * i]), all(st2[2 * i + 1]), back_inserter(st2[i]));
    }
    nextLifting = vv(N + 1, v(logN + 1, N));
    for (ll i = 0; i < N; i++) nextLifting[i][0] = nextHigher[i];
    for (ll i = 1; i <= logN; i++)
    {
        for (ll j = 0; j < N; j++)
        {
            nextLifting[j][i] = nextLifting[nextLifting[j][i - 1]][i - 1];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    ll mini = INF;
    for (ll j = C; j <= D; j++)
    {
        ll i = largestSmaller(A, B, H[j], st2);
        if (i == -1 || query(i, j - 1, st, true) > H[j]) continue;
        ll steps = 0;
        ll cur = i;
        for (ll k = logN; k >= 0; k--)
        {
            if (largestLifting[cur][k] != -1 && H[largestLifting[cur][k]] <= H[j])
            {
                cur = largestLifting[cur][k];
                steps += (1 << k);
            }
        }
        steps += abs(rightHeight[cur] - rightHeight[j]);
        mini = min(mini, steps);
    }
    if (mini == INF) mini = -1;
    return mini;
}
/*
int main() {
  int N, Q;
  assert(2 == scanf("%d %d", &N, &Q));
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &H[i]));
  }
  init(N, H);

  for (int i = 0; i < Q; ++i) {
    int A, B, C, D;
    assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
    printf("%d\n", minimum_jumps(A, B, C, D));
  }
  return 0;
}
/**/

Compilation message

jumps.cpp:224:1: warning: "/*" within comment [-Wcomment]
  224 | /**/
      |  
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:117:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for (ll i = 0; i < hSorted.size(); i++) H[hSorted[i].s] = i;
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 4042 ms 124296 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 196 ms 122468 KB Output is correct
6 Correct 356 ms 148108 KB Output is correct
7 Correct 108 ms 71260 KB Output is correct
8 Correct 318 ms 147892 KB Output is correct
9 Correct 31 ms 19372 KB Output is correct
10 Correct 404 ms 147448 KB Output is correct
11 Correct 277 ms 149952 KB Output is correct
12 Correct 344 ms 150256 KB Output is correct
13 Correct 246 ms 150596 KB Output is correct
14 Correct 355 ms 147648 KB Output is correct
15 Correct 272 ms 147544 KB Output is correct
16 Correct 235 ms 146968 KB Output is correct
17 Correct 235 ms 147008 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Incorrect 1 ms 344 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 305 ms 64772 KB Output is correct
5 Correct 1269 ms 147228 KB Output is correct
6 Correct 606 ms 24496 KB Output is correct
7 Correct 1158 ms 147256 KB Output is correct
8 Correct 582 ms 50880 KB Output is correct
9 Correct 1163 ms 147624 KB Output is correct
10 Correct 1536 ms 150416 KB Output is correct
11 Correct 1333 ms 149784 KB Output is correct
12 Correct 1461 ms 149796 KB Output is correct
13 Correct 1237 ms 148000 KB Output is correct
14 Correct 1304 ms 147804 KB Output is correct
15 Correct 879 ms 149892 KB Output is correct
16 Correct 802 ms 149112 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 2 ms 344 KB Output is correct
21 Correct 2 ms 596 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 14 ms 1484 KB Output is correct
28 Correct 11 ms 1368 KB Output is correct
29 Correct 13 ms 1508 KB Output is correct
30 Correct 14 ms 1504 KB Output is correct
31 Correct 10 ms 1528 KB Output is correct
32 Correct 0 ms 596 KB Output is correct
33 Correct 120 ms 79688 KB Output is correct
34 Correct 244 ms 147512 KB Output is correct
35 Correct 205 ms 150264 KB Output is correct
36 Correct 225 ms 147884 KB Output is correct
37 Correct 238 ms 147736 KB Output is correct
38 Correct 203 ms 148620 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 305 ms 64772 KB Output is correct
5 Correct 1269 ms 147228 KB Output is correct
6 Correct 606 ms 24496 KB Output is correct
7 Correct 1158 ms 147256 KB Output is correct
8 Correct 582 ms 50880 KB Output is correct
9 Correct 1163 ms 147624 KB Output is correct
10 Correct 1536 ms 150416 KB Output is correct
11 Correct 1333 ms 149784 KB Output is correct
12 Correct 1461 ms 149796 KB Output is correct
13 Correct 1237 ms 148000 KB Output is correct
14 Correct 1304 ms 147804 KB Output is correct
15 Correct 879 ms 149892 KB Output is correct
16 Correct 802 ms 149112 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 2 ms 344 KB Output is correct
21 Correct 2 ms 596 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 14 ms 1484 KB Output is correct
28 Correct 11 ms 1368 KB Output is correct
29 Correct 13 ms 1508 KB Output is correct
30 Correct 14 ms 1504 KB Output is correct
31 Correct 10 ms 1528 KB Output is correct
32 Correct 0 ms 596 KB Output is correct
33 Correct 120 ms 79688 KB Output is correct
34 Correct 244 ms 147512 KB Output is correct
35 Correct 205 ms 150264 KB Output is correct
36 Correct 225 ms 147884 KB Output is correct
37 Correct 238 ms 147736 KB Output is correct
38 Correct 203 ms 148620 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 315 ms 64988 KB Output is correct
43 Correct 1195 ms 147480 KB Output is correct
44 Correct 541 ms 24516 KB Output is correct
45 Correct 1204 ms 147996 KB Output is correct
46 Correct 607 ms 50884 KB Output is correct
47 Correct 1195 ms 148224 KB Output is correct
48 Correct 1491 ms 149800 KB Output is correct
49 Correct 1296 ms 150556 KB Output is correct
50 Correct 1387 ms 149996 KB Output is correct
51 Correct 1294 ms 147640 KB Output is correct
52 Correct 1333 ms 147224 KB Output is correct
53 Correct 892 ms 148200 KB Output is correct
54 Correct 813 ms 148188 KB Output is correct
55 Correct 0 ms 344 KB Output is correct
56 Incorrect 291 ms 146948 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 4042 ms 124296 KB Time limit exceeded
4 Halted 0 ms 0 KB -