oj.uz

Submission #471918

# Submission time Handle Problem Language Result Execution time Memory
471918 2021-09-11T17:32:39 Z qwerasdfzxcl Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 2392 ms 170076 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;
    assert(ans);

    /*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 15 ms 28516 KB Output is correct
2 Correct 15 ms 28444 KB Output is correct
3 Correct 631 ms 140760 KB Output is correct
4 Correct 2392 ms 169896 KB Output is correct
5 Correct 1859 ms 99304 KB Output is correct
6 Correct 2323 ms 169972 KB Output is correct
7 Correct 1543 ms 124772 KB Output is correct
8 Correct 1956 ms 169864 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28476 KB Output is correct
2 Correct 16 ms 28440 KB Output is correct
3 Correct 15 ms 28488 KB Output is correct
4 Correct 16 ms 28488 KB Output is correct
5 Correct 17 ms 28488 KB Output is correct
6 Incorrect 20 ms 28636 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28476 KB Output is correct
2 Correct 16 ms 28440 KB Output is correct
3 Correct 15 ms 28488 KB Output is correct
4 Correct 16 ms 28488 KB Output is correct
5 Correct 17 ms 28488 KB Output is correct
6 Incorrect 20 ms 28636 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28488 KB Output is correct
2 Correct 16 ms 28488 KB Output is correct
3 Correct 16 ms 28428 KB Output is correct
4 Correct 19 ms 28456 KB Output is correct
5 Correct 462 ms 142104 KB Output is correct
6 Correct 572 ms 169980 KB Output is correct
7 Correct 294 ms 100416 KB Output is correct
8 Correct 575 ms 170036 KB Output is correct
9 Correct 87 ms 49344 KB Output is correct
10 Correct 568 ms 170048 KB Output is correct
11 Correct 548 ms 170044 KB Output is correct
12 Correct 544 ms 170048 KB Output is correct
13 Incorrect 550 ms 170076 KB Output isn't correct
14 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 16 ms 28424 KB Output is correct
3 Correct 16 ms 28488 KB Output is correct
4 Incorrect 498 ms 92752 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 16 ms 28424 KB Output is correct
3 Correct 16 ms 28488 KB Output is correct
4 Incorrect 498 ms 92752 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28516 KB Output is correct
2 Correct 15 ms 28444 KB Output is correct
3 Correct 631 ms 140760 KB Output is correct
4 Correct 2392 ms 169896 KB Output is correct
5 Correct 1859 ms 99304 KB Output is correct
6 Correct 2323 ms 169972 KB Output is correct
7 Correct 1543 ms 124772 KB Output is correct
8 Correct 1956 ms 169864 KB Output is correct
9 Correct 16 ms 28476 KB Output is correct
10 Correct 16 ms 28440 KB Output is correct
11 Correct 15 ms 28488 KB Output is correct
12 Correct 16 ms 28488 KB Output is correct
13 Correct 17 ms 28488 KB Output is correct
14 Incorrect 20 ms 28636 KB Output isn't correct
15 Halted 0 ms 0 KB -