oj.uz

Submission #471913

# Submission time Handle Problem Language Result Execution time Memory
471913 2021-09-11T16:55:37 Z qwerasdfzxcl Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 170048 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 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;
    /*cur2 = C, cur3 = -1;
    for (int j=19;j>=0;j--) if (cur2+(1<<j)-1<=D && max(sp2[cur2][j], cur3)<a[cur]){
        cur3 = max(sp2[cur2][j], cur3);
        cur2 += (1<<j);
    }
    C = cur2;*/

    /*for (int j=19;j>=0;j--) if (sp3[cur][j]!=-1 && a[sp3[cur][j]]<mx && sp3[cur][j]<C) cur = sp3[cur][j], ans += (1<<j);
    for (int j=19;j>=0;j--) if (sp4[cur][j]!=n && a[sp4[cur][j]]<mx && sp4[cur][j]<C) cur = sp4[cur][j], ans += (1<<j);
    if (cur==-1 || cur==n) return -1;
    cur = sp4[cur][0], ans++;
    if (cur<C || cur>D) return -1;*/

    int ret = -1, tmp3 = 0;
    while(cur!=-1 && a[cur]<=mx){
        cur2 = cur, ans = tmp3;
        for (int j=19;j>=0;j--) if (sp4[cur2][j]!=n && a[sp4[cur2][j]]<mx && sp4[cur2][j]<C) cur2 = sp4[cur2][j], ans += (1<<j);
        if (cur2==-1 || cur2==n){
            cur = sp3[cur][0];
            tmp3++;
            continue;
        }
        cur2 = sp4[cur2][0], ans++;
        if (cur2<C || cur2>D){
            cur = sp3[cur][0];
            tmp3++;
            continue;
        }
        ret = max(ret, ans);

        cur = sp3[cur][0];
        tmp3++;
    }
    return ret;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28488 KB Output is correct
2 Correct 15 ms 28488 KB Output is correct
3 Execution timed out 4051 ms 140896 KB Time limit exceeded
4 Halted 0 ms 0 KB -

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 18 ms 28472 KB Output is correct
4 Correct 16 ms 28488 KB Output is correct
5 Incorrect 17 ms 28488 KB Output isn't correct
6 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 18 ms 28472 KB Output is correct
4 Correct 16 ms 28488 KB Output is correct
5 Incorrect 17 ms 28488 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28420 KB Output is correct
2 Correct 15 ms 28488 KB Output is correct
3 Correct 17 ms 28480 KB Output is correct
4 Correct 20 ms 28488 KB Output is correct
5 Correct 478 ms 142164 KB Output is correct
6 Correct 611 ms 169916 KB Output is correct
7 Correct 320 ms 100468 KB Output is correct
8 Correct 600 ms 170048 KB Output is correct
9 Correct 94 ms 49456 KB Output is correct
10 Correct 596 ms 169952 KB Output is correct
11 Incorrect 650 ms 169940 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 15 ms 28432 KB Output is correct
4 Incorrect 555 ms 92740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.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 15 ms 28432 KB Output is correct
4 Incorrect 555 ms 92740 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 28488 KB Output is correct
2 Correct 15 ms 28488 KB Output is correct
3 Execution timed out 4051 ms 140896 KB Time limit exceeded
4 Halted 0 ms 0 KB -