oj.uz

Submission #471919

# Submission time Handle Problem Language Result Execution time Memory
471919 2021-09-11T17:34:46 Z qwerasdfzxcl Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 2351 ms 169984 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;
    if (a[cur]>mx) return -1;

    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 28488 KB Output is correct
2 Correct 16 ms 28476 KB Output is correct
3 Correct 560 ms 140832 KB Output is correct
4 Correct 2274 ms 169880 KB Output is correct
5 Correct 1912 ms 99224 KB Output is correct
6 Correct 2351 ms 169948 KB Output is correct
7 Correct 1738 ms 124776 KB Output is correct
8 Correct 2301 ms 169868 KB Output is correct

Subtask #2
0 / 8.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 17 ms 28468 KB Output is correct
4 Correct 16 ms 28488 KB Output is correct
5 Correct 19 ms 28504 KB Output is correct
6 Incorrect 19 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 16 ms 28488 KB Output is correct
2 Correct 16 ms 28488 KB Output is correct
3 Correct 17 ms 28468 KB Output is correct
4 Correct 16 ms 28488 KB Output is correct
5 Correct 19 ms 28504 KB Output is correct
6 Incorrect 19 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 17 ms 28488 KB Output is correct
3 Correct 17 ms 28488 KB Output is correct
4 Correct 17 ms 28488 KB Output is correct
5 Correct 462 ms 142008 KB Output is correct
6 Correct 588 ms 169888 KB Output is correct
7 Correct 302 ms 100456 KB Output is correct
8 Correct 575 ms 169920 KB Output is correct
9 Correct 110 ms 49372 KB Output is correct
10 Correct 597 ms 169984 KB Output is correct
11 Correct 554 ms 169956 KB Output is correct
12 Correct 571 ms 169872 KB Output is correct
13 Incorrect 568 ms 169876 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 28436 KB Output is correct
2 Correct 16 ms 28508 KB Output is correct
3 Correct 16 ms 28488 KB Output is correct
4 Incorrect 543 ms 92660 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 28436 KB Output is correct
2 Correct 16 ms 28508 KB Output is correct
3 Correct 16 ms 28488 KB Output is correct
4 Incorrect 543 ms 92660 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 28488 KB Output is correct
2 Correct 16 ms 28476 KB Output is correct
3 Correct 560 ms 140832 KB Output is correct
4 Correct 2274 ms 169880 KB Output is correct
5 Correct 1912 ms 99224 KB Output is correct
6 Correct 2351 ms 169948 KB Output is correct
7 Correct 1738 ms 124776 KB Output is correct
8 Correct 2301 ms 169868 KB Output is correct
9 Correct 16 ms 28488 KB Output is correct
10 Correct 16 ms 28488 KB Output is correct
11 Correct 17 ms 28468 KB Output is correct
12 Correct 16 ms 28488 KB Output is correct
13 Correct 19 ms 28504 KB Output is correct
14 Incorrect 19 ms 28616 KB Output isn't correct
15 Halted 0 ms 0 KB -