oj.uz

Submission #458031

# Submission time Handle Problem Language Result Execution time Memory
458031 2021-08-07T19:34:36 Z wiwiho Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1487 ms 89604 KB 
#include "jumps.h"

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

int SZ = 20;
int n;
struct Doubling{
    vector<vector<int>> a, mx;
    void resize(){
        a.resize(SZ, vector<int>(n));
        mx.resize(SZ, vector<int>(n));
    }
    void init(){
        for(int i = 0; i < n; i++) mx[0][i] = a[0][i];
        for(int i = 1; i < SZ; i++){
            for(int j = 0; j < n; j++){
                if(a[i - 1][j] == -1){
                    a[i][j] = -1;
                    continue;
                }
                a[i][j] = a[i - 1][a[i - 1][j]];
                mx[i][j] = max(mx[i - 1][j], mx[i - 1][a[i - 1][j]]);
            }
        }
    }
    int& operator()(int i, int j){
        return a[i][j];
    }
};

struct SparseTable{
    vector<vector<int>> st;
    vector<int> a;
    int maxarg(int p, int q){
        return a[p] > a[q] ? p : q;
    }
    void init(vector<int>& _a){
        a = _a;
        st.resize(SZ, vector<int>(n));
        for(int i = 0; i < n; i++) st[0][i] = i;
        for(int i = 1; i < SZ; i++){
            for(int j = 0; j + (1 << i) - 1 < n; j++){
                st[i][j] = maxarg(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    int query(int l, int r){
        int lg = __lg(r - l + 1);
        return maxarg(st[lg][l], st[lg][r - (1 << lg) + 1]);
    }
};

Doubling small, large;
SparseTable st;
vector<int> mn, mx;

int dfs(int l, int r, int lp, int rp, int p){
    if(l > r) return p;
    int pos = st.query(l, r);
    mn[pos] = l;
    mx[pos] = r;
    small(0, pos) = p;
    large(0, pos) = p ^ lp ^ rp;
    dfs(l, pos - 1, lp, pos, pos);
    dfs(pos + 1, r, pos, rp, pos);
    return pos;
}

void init(int N, vector<int> H){
    n = N;
    mn.resize(n);
    mx.resize(n);
    st.init(H);
    small.resize();
    large.resize();
    dfs(0, n - 1, -1, -1, -1);
    small.init();
    large.init();
//    printv(small.a[0], cerr);
//    printv(large.a[0], cerr);
}

int minimum_jumps(int A, int B, int C, int D){

    int ed = st.query(C, D);
    A = max(A, mn[ed]);
    if(A > B) return -1;

    int start = st.query(A, B);
    if(mx[start] >= C){
        int tmp = st.query(C, mx[start]);
        if(mn[tmp] <= B){
            assert(C <= small(0, start) || C <= large(0, start));
            return 1;
        }
    }
//    cerr << "start " << start << "\n";
    if(C <= small(0, start)) return 1;

    int ans = 0;
    for(int i = SZ - 1; i >= 0; i--){
        if(large(i, start) != -1 && mn[ed] <= large(i, start) && large(i, start) <= mx[ed] && large.mx[i][start] < C){
            ans += 1 << i;
            start = large(i, start);
            assert(mn[ed] <= start && start <= mx[ed]);
        }
    }

    if(large(0, start) != -1 && mn[ed] <= large(0, start) && large(0, start) <= mx[ed]){
        start = large(0, start);
    }
    if(start >= C) return ans;

    for(int i = SZ - 1; i >= 0; i--){
        if(small(i, start) != -1 && small.mx[i][start] < C){
            ans += 1 << i;
            start = small(i, start);
        }
    }
    start = small(0, start);
    assert(C <= start && start <= D);
//    cerr << "end " << small(0, start) << "\n";

    return ans + 1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 219 ms 71332 KB Output is correct
4 Correct 1487 ms 89472 KB Output is correct
5 Correct 1209 ms 45180 KB Output is correct
6 Correct 1263 ms 89604 KB Output is correct
7 Correct 1010 ms 61204 KB Output is correct
8 Correct 1304 ms 89580 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Incorrect 2 ms 200 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 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Incorrect 2 ms 200 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 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 67 ms 66984 KB Output is correct
6 Correct 88 ms 83248 KB Output is correct
7 Correct 42 ms 42760 KB Output is correct
8 Correct 82 ms 83320 KB Output is correct
9 Correct 15 ms 12744 KB Output is correct
10 Correct 83 ms 83204 KB Output is correct
11 Correct 87 ms 89488 KB Output is correct
12 Correct 98 ms 87880 KB Output is correct
13 Correct 85 ms 87684 KB Output is correct
14 Correct 84 ms 83224 KB Output is correct
15 Incorrect 116 ms 89588 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 219 ms 71332 KB Output is correct
4 Correct 1487 ms 89472 KB Output is correct
5 Correct 1209 ms 45180 KB Output is correct
6 Correct 1263 ms 89604 KB Output is correct
7 Correct 1010 ms 61204 KB Output is correct
8 Correct 1304 ms 89580 KB Output is correct
9 Correct 0 ms 200 KB Output is correct
10 Correct 0 ms 200 KB Output is correct
11 Correct 0 ms 200 KB Output is correct
12 Correct 0 ms 200 KB Output is correct
13 Incorrect 2 ms 200 KB Output isn't correct
14 Halted 0 ms 0 KB -