oj.uz

Submission #557198

# Submission time Handle Problem Language Result Execution time Memory
557198 2022-05-04T20:58:05 Z new_acc Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1018 ms 33568 KB 
#include<bits/stdc++.h>
#include "jumps.h"
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e5+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=18;
int t[N],l[N][L+1],r[N][L+1],n;
void init(int nn,vi v){
    n=nn;
    for(int i=1;i<=n;i++) t[i]=v[i-1];
    deque<pair<int,int> >deq;
    for(int i=n;i>=1;i--){
        while(deq.size() and deq.back().fi<t[i]) deq.pop_back();
        if(!deq.size()) r[i][0]=n+1;
        else r[i][0]=deq.back().se;
        deq.push_back({t[i],i});
    }
    deq.clear();
    for(int i=1;i<=n;i++){
        while(deq.size() and deq.back().fi<t[i]) deq.pop_back();
        if(!deq.size()) l[i][0]=0;
        else l[i][0]=deq.back().se;
        deq.push_back({t[i],i});
    }
    for(int i=0;i<=L;i++) r[n+1][i]=n+1;
    for(int i=1;i<=n;i++){
        for(int k=1;k<=L;k++) l[i][k]=l[l[i][k-1]][k-1];
    }
    for(int i=n;i>=1;i--){
        for(int k=1;k<=L;k++) r[i][k]=r[r[i][k-1]][k-1];
    }
}
int minimum_jumps(int a,int b,int c,int d){
    a++,b++,c++,d++;
    int cc=c;
    for(int i=L;i>=0;i--) if(r[cc][i]<=d) cc=r[cc][i];
    if(t[b]>t[cc]) return -1;
    int bb=b;
    for(int i=L;i>=0;i--) if(l[bb][i]>=a and t[l[bb][i]]<t[cc]) bb=l[bb][i];
    int res=-1,curr=0;
    for(int i=L;i>=0;i--){
        if(r[bb][i]<c) curr+=(1<<i),bb=r[bb][i];
        else res=curr+(1<<i);
    }
    if(r[bb][0]>d) return -1;
    return res;
}
/*int main(){
    int n;
    cin>>n;
    vi xd;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        xd.push_back(a);
    }
    init(n,xd);
    int q;
    cin>>q;
    while(q--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        cout<<minimum_jumps(a,b,c,d)<<"\n";
    }
}*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 141 ms 26828 KB Output is correct
4 Correct 968 ms 33536 KB Output is correct
5 Correct 719 ms 17060 KB Output is correct
6 Correct 1018 ms 33408 KB Output is correct
7 Correct 776 ms 23176 KB Output is correct
8 Correct 957 ms 33448 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 2 ms 208 KB Output is correct
6 Incorrect 2 ms 336 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 2 ms 208 KB Output is correct
6 Incorrect 2 ms 336 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 54 ms 26020 KB Output is correct
6 Correct 71 ms 32308 KB Output is correct
7 Correct 32 ms 16680 KB Output is correct
8 Correct 65 ms 32328 KB Output is correct
9 Correct 10 ms 5108 KB Output is correct
10 Correct 73 ms 32284 KB Output is correct
11 Correct 65 ms 33392 KB Output is correct
12 Correct 64 ms 33568 KB Output is correct
13 Incorrect 62 ms 33420 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 260 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 221 ms 14872 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 260 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 221 ms 14872 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 141 ms 26828 KB Output is correct
4 Correct 968 ms 33536 KB Output is correct
5 Correct 719 ms 17060 KB Output is correct
6 Correct 1018 ms 33408 KB Output is correct
7 Correct 776 ms 23176 KB Output is correct
8 Correct 957 ms 33448 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 2 ms 208 KB Output is correct
14 Incorrect 2 ms 336 KB Output isn't correct
15 Halted 0 ms 0 KB -