oj.uz

답안 #458014

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
458014 2021-08-07T18:33:06 Z wiwiho 밀림 점프 (APIO21_jumps) C++14
4 / 100
 1547 ms 89576 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) return 1;
    }
//    cerr << "start " << start << "\n";

    int ans = 0;
    for(int i = SZ - 1; i >= 0; i--){
        if(large(i, start) != -1 && mn[ed] <= large(i, start)){
            ans += 1 << i;
            start = large(i, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 304 ms 71448 KB Output is correct
4 Correct 1322 ms 89492 KB Output is correct
5 Correct 1303 ms 45256 KB Output is correct
6 Correct 1395 ms 89472 KB Output is correct
7 Correct 1071 ms 61176 KB Output is correct
8 Correct 1547 ms 89492 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct
4 Correct 2 ms 200 KB Output is correct
5 Correct 3 ms 200 KB Output is correct
6 Incorrect 4 ms 328 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct
4 Correct 2 ms 200 KB Output is correct
5 Correct 3 ms 200 KB Output is correct
6 Incorrect 4 ms 328 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 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 Correct 68 ms 67116 KB Output is correct
6 Correct 90 ms 83284 KB Output is correct
7 Correct 67 ms 42756 KB Output is correct
8 Correct 85 ms 83248 KB Output is correct
9 Correct 51 ms 12736 KB Output is correct
10 Correct 118 ms 83340 KB Output is correct
11 Correct 87 ms 89544 KB Output is correct
12 Correct 103 ms 87956 KB Output is correct
13 Correct 88 ms 87744 KB Output is correct
14 Correct 83 ms 83224 KB Output is correct
15 Incorrect 107 ms 89576 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Incorrect 336 ms 38276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Incorrect 336 ms 38276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 304 ms 71448 KB Output is correct
4 Correct 1322 ms 89492 KB Output is correct
5 Correct 1303 ms 45256 KB Output is correct
6 Correct 1395 ms 89472 KB Output is correct
7 Correct 1071 ms 61176 KB Output is correct
8 Correct 1547 ms 89492 KB Output is correct
9 Correct 0 ms 200 KB Output is correct
10 Correct 0 ms 200 KB Output is correct
11 Correct 2 ms 200 KB Output is correct
12 Correct 2 ms 200 KB Output is correct
13 Correct 3 ms 200 KB Output is correct
14 Incorrect 4 ms 328 KB Output isn't correct
15 Halted 0 ms 0 KB -