oj.uz

Submission #471915

# Submission time Handle Problem Language Result Execution time Memory
471915 2021-09-11T17:27:00 Z qwerasdfzxcl Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 2429 ms 170068 KB 
#include "jumps.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int> sp1[200200], sp2[200200], sp3[200200], sp4[200200], a;
int n, l[200200], r[200200], INV[200200];
struct MST{
    vector<int> tree[400400];
    int sz;
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i].push_back(a[i-sz]);
        for (int i=sz-1;i;i--){
            tree[i].resize(tree[i<<1].size()+tree[i<<1|1].size());
            merge(tree[i<<1].begin(), tree[i<<1].end(), tree[i<<1|1].begin(), tree[i<<1|1].end(), tree[i].begin());
        }
    }
    int query(int l, int r, int x){
        int ret = -1;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1){
                auto iter = lower_bound(tree[l].begin(), tree[l].end(), x);
                if (iter!=tree[l].begin()) ret = max(ret, *(--iter));
                l++;
            }
            if (r&1){
                --r;
                auto iter = lower_bound(tree[r].begin(), tree[r].end(), x);
                if (iter!=tree[r].begin()) ret = max(ret, *(--iter));
            }
        }
        return ret;
    }
    int query2(int l, int r){
        int ret = -1;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1){
                ret = max(ret, tree[l].back());
                l++;
            }
            if (r&1){
                --r;
                ret = max(ret, tree[r].back());
            }
        }
        return ret;
    }
}tree;

int geth(int x){
    if (x<0) return -1e9;
    if (x>=n) return -1e9;
    return a[x];
}

void init(int N, std::vector<int> H) {
    n = N, a = H;
    for (int i=0;i<n;i++){
        INV[H[i]] = i;
        sp1[i].push_back(H[i]);
        sp2[i].push_back(H[i]);
    }
    for (int j=1;j<20;j++){
        for (int i=0;i<n;i++){
            if (i-(1<<j)+1<0) sp1[i].push_back(-1);
            else sp1[i].push_back(max(sp1[i][j-1], sp1[i-(1<<(j-1))][j-1]));
            if (i+(1<<j)-1>=n) sp2[i].push_back(-1);
            else sp2[i].push_back(max(sp2[i][j-1], sp2[i+(1<<(j-1))][j-1]));
        }
    }
    for (int i=0;i<n;i++){
        int cur = i-1, cur2 = -1e9;
        for (int j=19;j>=0;j--) if (cur!=-1 && sp1[cur][j]!=-1 && max(cur2, sp1[cur][j])<H[i]){
            cur2 = max(cur2, sp1[cur][j]);
            cur -= (1<<j);
        }
        l[i] = cur; cur = i+1, cur2 = -1e9;
        for (int j=19;j>=0;j--) if (cur!=n && sp2[cur][j]!=-1 && sp2[cur][j]<H[i]){
            cur2 = max(cur2, sp1[cur][j]);
            cur += (1<<j);
        }
        r[i] = cur;
        if (geth(l[i])>=geth(r[i])) sp3[i].push_back(l[i]);
        else sp3[i].push_back(r[i]);
        sp4[i].push_back(r[i]);
        //printf("%d %d\n", l[i], r[i]);
    }
    for (int j=1;j<20;j++){
        for (int i=0;i<n;i++){
            if (sp3[i][j-1]==-1) sp3[i].push_back(-1);
            else sp3[i].push_back(sp3[sp3[i][j-1]][j-1]);
            if (sp4[i][j-1]==n) sp4[i].push_back(n);
            else sp4[i].push_back(sp4[sp4[i][j-1]][j-1]);
        }
    }
    tree.init(n);
}

int query(int A, int C){
    int cur = A, ans = 0;
    if (A>C){
        for (int j=19;j>=0;j--) if (sp3[cur][j]!=-1 && a[sp3[cur][j]]<=a[C]) cur = sp3[cur][j], ans += (1<<j);
        if (cur!=C) return 1e9;
        return ans;
    }
    for (int j=19;j>=0;j--) if (sp3[cur][j]!=-1 && a[sp3[cur][j]]<a[C]) cur = sp3[cur][j], ans += (1<<j);
    for (int j=19;j>=0;j--) if (sp4[cur][j]!=n && a[sp4[cur][j]]<=a[C]) cur = sp4[cur][j], ans += (1<<j);
    if (cur!=C) return -1;
    return ans;
}

int minimum_jumps(int A, int B, int C, int D) {
    int mx = tree.query2(C, D+1);
    int cur2 = B, cur3 = -1;
    for (int j=19;j>=0;j--) if (cur2-(1<<j)+1>=A && max(sp1[cur2][j], cur3)<mx){
        cur3 = max(sp1[cur2][j], cur3);
        cur2 -= (1<<j);
    }
    A = cur2+1;
    int tmp = tree.query(A, B+1, mx);
    if (tmp==-1) return -1;

    int cur = INV[tmp], ans = 0;

    int val1 = tree.query2(cur+1, C);
    if (val1<a[cur]) return 1;
    if (val1>mx) return -1;
    ans = query(cur, INV[val1])+1;

    cur2 = cur, cur3 = -1;
    for (int j=19;j>=0;j--) if (cur2-(1<<j)+1>=0 && max(sp1[cur2][j], cur3)<val1){
        cur3 = max(sp1[cur2][j], cur3);
        cur2 -= (1<<j);
    }
    if (cur2!=-1) ans = min(ans, query(cur, cur2)+1);
    return ans;

}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28416 KB Output is correct
2 Correct 15 ms 28488 KB Output is correct
3 Correct 655 ms 140824 KB Output is correct
4 Correct 2224 ms 169964 KB Output is correct
5 Correct 1798 ms 99248 KB Output is correct
6 Correct 2429 ms 169964 KB Output is correct
7 Correct 1778 ms 124888 KB Output is correct
8 Correct 2134 ms 169908 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28488 KB Output is correct
2 Correct 17 ms 28556 KB Output is correct
3 Correct 16 ms 28488 KB Output is correct
4 Correct 17 ms 28488 KB Output is correct
5 Correct 18 ms 28488 KB Output is correct
6 Incorrect 18 ms 28616 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28488 KB Output is correct
2 Correct 17 ms 28556 KB Output is correct
3 Correct 16 ms 28488 KB Output is correct
4 Correct 17 ms 28488 KB Output is correct
5 Correct 18 ms 28488 KB Output is correct
6 Incorrect 18 ms 28616 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28488 KB Output is correct
2 Correct 19 ms 28408 KB Output is correct
3 Correct 17 ms 28456 KB Output is correct
4 Correct 17 ms 28488 KB Output is correct
5 Correct 451 ms 142148 KB Output is correct
6 Correct 566 ms 169944 KB Output is correct
7 Correct 291 ms 100428 KB Output is correct
8 Correct 569 ms 170068 KB Output is correct
9 Correct 87 ms 49412 KB Output is correct
10 Correct 578 ms 169924 KB Output is correct
11 Correct 552 ms 169956 KB Output is correct
12 Incorrect 545 ms 169872 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28488 KB Output is correct
2 Correct 15 ms 28488 KB Output is correct
3 Correct 17 ms 28416 KB Output is correct
4 Incorrect 403 ms 92732 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28488 KB Output is correct
2 Correct 15 ms 28488 KB Output is correct
3 Correct 17 ms 28416 KB Output is correct
4 Incorrect 403 ms 92732 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28416 KB Output is correct
2 Correct 15 ms 28488 KB Output is correct
3 Correct 655 ms 140824 KB Output is correct
4 Correct 2224 ms 169964 KB Output is correct
5 Correct 1798 ms 99248 KB Output is correct
6 Correct 2429 ms 169964 KB Output is correct
7 Correct 1778 ms 124888 KB Output is correct
8 Correct 2134 ms 169908 KB Output is correct
9 Correct 17 ms 28488 KB Output is correct
10 Correct 17 ms 28556 KB Output is correct
11 Correct 16 ms 28488 KB Output is correct
12 Correct 17 ms 28488 KB Output is correct
13 Correct 18 ms 28488 KB Output is correct
14 Incorrect 18 ms 28616 KB Output isn't correct
15 Halted 0 ms 0 KB -