Submission #1031830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031830		mispertion	Rainforest Jumps (APIO21_jumps)	C++17	23 / 100	4042 ms	69496 KiB

jumps

#include "jumps.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstdio>

using namespace std;
 
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
 
const ld PI = 3.1415926535;
const int N = 5e5+10;
const int M = 1e4 + 5;
int mod = 1e9+7;
const int P = 467743;

const int K = 20;
int h[N], n, lu[N], ru[N], up1[N][K], up2[N][K], whr[N];

struct sparset{
    int st[N][K];
    int mx[N][K];
    void init(){
        for(int i = 1; i <= n; i++)
            st[i][0] = h[i], mx[i][0] = h[i];
        for(int k = 1; k < K; k++)
            for(int i = 1; i + (1 << k) - 1 <= n; i++)
                st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
        for(int k = 1; k < K; k++)
            for(int i = 1; i + (1 << k) - 1 <= n; i++)
                mx[i][k] = max(mx[i][k - 1], mx[i + (1 << (k - 1))][k - 1]);
    }

    int getmn(int l, int r){
        int g = __lg(r - l + 1);
        return min(st[l][g], st[r - (1 << g) + 1][g]);
    }
    
    int getmx(int l, int r){
        int g = __lg(r - l + 1);
        return max(mx[l][g], mx[r - (1 << g) + 1][g]);
    }
} st;

void init(int _n, std::vector<int> H) {
    n = _n;
    for(int i = 0; i < n; i++)
        h[i + 1] = H[i], whr[H[i]] = i + 1;
    vector<pii> ps = {};
    st.init();
    for(int i = 1; i <= n; i++){
        ps.pb({h[i], i});
        int lo = 0, hi = i;
        while(lo + 1 < hi){
            int m = (lo + hi) / 2;
            if(st.getmx(m, i) > h[i])
                lo = m;
            else
                hi = m;
        }
        lu[i] = lo;
        lo = i, hi = n + 1;
        while(lo + 1 < hi){
            int m = (lo + hi) / 2;
            if(st.getmx(i, m) > h[i])
                hi = m;
            else
                lo = m;
        }
        ru[i] = hi;
    }
    sort(all(ps));
    for(int k = 0; k < K; k++)
        up1[n + 1][k] = up2[n + 1][k] = n + 1;
    ru[n + 1] = n + 1;
    for(int i = sz(ps) - 1; i >= 0; i--){
        int pos = ps[i].S;
        if(lu[pos] == 0 && ru[pos] == n + 1){
            for(int k = 0; k < K; k++)
                up1[pos][k] = n + 1;
        }else if(lu[pos] == 0){
            up1[pos][0] = ru[pos];
            for(int k = 1; k < K; k++)
                up1[pos][k] = up1[up1[pos][k - 1]][k - 1];
        }else if(ru[pos] == n + 1){
            up1[pos][0] = lu[pos];
            for(int k = 1; k < K; k++)
                up1[pos][k] = up1[up1[pos][k - 1]][k - 1];
        }else{
            if(h[lu[pos]] > h[ru[pos]])
                up1[pos][0] = lu[pos];
            else
                up1[pos][0] = ru[pos];
            for(int k = 1; k < K; k++)
                up1[pos][k] = up1[up1[pos][k - 1]][k - 1];
        }
    }
    for(int i = n; i >= 1; i--){
        up2[i][0] = ru[i];
        for(int k = 1; k < K; k++){
            up2[i][k] = up2[up2[i][k - 1]][k - 1];
        }
    }
}

int getans(int st, int C, int D){
    int ret = 0;
    for(int k = K - 1; k >= 0; k--){
        if(ru[up1[st][k]] < C)
            st = up1[st][k], ret += (1 << k);
    }
    if(ru[up1[st][0]] <= D){
        return ret + 2;
    }
    for(int k = K - 1; k >= 0; k--){
        if(up2[st][k] < C)
            st = up2[st][k], ret += (1 << k);
    }
    if(ru[st] <= D){
        return ret + 1;
    }
    return -1;
}

int minimum_jumps(int A, int B, int C, int D) {
    A++;
    B++;
    C++;
    D++;
    int ret = -1;
    for(int i = A; i <= B; i++){
        int r = getans(i, C, D);
        if(r == -1)
            continue;
        if(ret == -1){
            ret = r;
        }else{
            ret = min(ret, r);
        }
    }
    return ret;
}


/*signed 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;
}*/

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 23 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19