oj.uz

Submission #471917

# Submission time Handle Problem Language Result Execution time Memory
471917 2021-09-11T17:30:32 Z qwerasdfzxcl Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 2417 ms 170084 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 18 ms 28508 KB Output is correct
2 Correct 18 ms 28404 KB Output is correct
3 Correct 638 ms 140880 KB Output is correct
4 Correct 2033 ms 169924 KB Output is correct
5 Correct 1807 ms 99296 KB Output is correct
6 Correct 2212 ms 169880 KB Output is correct
7 Correct 1946 ms 124744 KB Output is correct
8 Correct 2417 ms 169972 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28520 KB Output is correct
2 Correct 21 ms 28504 KB Output is correct
3 Correct 22 ms 28512 KB Output is correct
4 Correct 18 ms 28488 KB Output is correct
5 Correct 18 ms 28416 KB Output is correct
6 Incorrect 21 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 19 ms 28520 KB Output is correct
2 Correct 21 ms 28504 KB Output is correct
3 Correct 22 ms 28512 KB Output is correct
4 Correct 18 ms 28488 KB Output is correct
5 Correct 18 ms 28416 KB Output is correct
6 Incorrect 21 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 17 ms 28508 KB Output is correct
2 Correct 20 ms 28416 KB Output is correct
3 Correct 20 ms 28448 KB Output is correct
4 Correct 19 ms 28488 KB Output is correct
5 Correct 490 ms 142016 KB Output is correct
6 Correct 633 ms 169956 KB Output is correct
7 Correct 323 ms 100508 KB Output is correct
8 Correct 615 ms 170084 KB Output is correct
9 Correct 98 ms 49468 KB Output is correct
10 Correct 622 ms 169892 KB Output is correct
11 Correct 603 ms 169896 KB Output is correct
12 Correct 583 ms 169888 KB Output is correct
13 Incorrect 581 ms 169964 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28488 KB Output is correct
2 Correct 19 ms 28488 KB Output is correct
3 Correct 18 ms 28404 KB Output is correct
4 Incorrect 565 ms 92656 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28488 KB Output is correct
2 Correct 19 ms 28488 KB Output is correct
3 Correct 18 ms 28404 KB Output is correct
4 Incorrect 565 ms 92656 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28508 KB Output is correct
2 Correct 18 ms 28404 KB Output is correct
3 Correct 638 ms 140880 KB Output is correct
4 Correct 2033 ms 169924 KB Output is correct
5 Correct 1807 ms 99296 KB Output is correct
6 Correct 2212 ms 169880 KB Output is correct
7 Correct 1946 ms 124744 KB Output is correct
8 Correct 2417 ms 169972 KB Output is correct
9 Correct 19 ms 28520 KB Output is correct
10 Correct 21 ms 28504 KB Output is correct
11 Correct 22 ms 28512 KB Output is correct
12 Correct 18 ms 28488 KB Output is correct
13 Correct 18 ms 28416 KB Output is correct
14 Incorrect 21 ms 28616 KB Output isn't correct
15 Halted 0 ms 0 KB -