oj.uz

Submission #557224

# Submission time Handle Problem Language Result Execution time Memory
557224 2022-05-04T21:45:58 Z new_acc Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1192 ms 48484 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],w[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];
    }
    t[n+1]=INFi;
    for(int i=1;i<=n;i++){
        if((r[i][0]==n+1 and l[i][0]!=0) or t[l[i][0]]>t[r[i][0]]) w[i][0]=l[i][0];
        else w[i][0]=r[i][0];
    }
    for(int i=0;i<=L;i++) w[n+1][i]=n+1;
    for(int i=1;i<=L;i++){
        for(int k=1;k<=n;k++) w[k][i]=w[w[k][i-1]][i-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];
    cc=c;
    for(int i=L;i>=0;i--) if(r[cc][i]<=d and t[r[cc][i]]<t[bb]) cc=r[cc][i];
    cc=r[cc][0];
    int curr=0;
    for(int i=L;i>=0;i--) if(t[w[bb][i]]<t[cc] and w[bb][i]<c) bb=w[bb][i],curr+=(1<<i);
    int res=-1;
    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 164 ms 38732 KB Output is correct
4 Correct 1080 ms 48216 KB Output is correct
5 Correct 874 ms 24544 KB Output is correct
6 Correct 1192 ms 48484 KB Output is correct
7 Correct 867 ms 33396 KB Output is correct
8 Correct 1008 ms 48256 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 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 2 ms 208 KB Output isn't correct
6 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 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 2 ms 208 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 78 ms 38044 KB Output is correct
6 Correct 98 ms 47264 KB Output is correct
7 Correct 50 ms 24264 KB Output is correct
8 Correct 108 ms 47220 KB Output is correct
9 Correct 12 ms 7376 KB Output is correct
10 Correct 98 ms 47140 KB Output is correct
11 Correct 102 ms 48436 KB Output is correct
12 Correct 107 ms 48300 KB Output is correct
13 Incorrect 98 ms 48260 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 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 256 ms 21772 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 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 256 ms 21772 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 164 ms 38732 KB Output is correct
4 Correct 1080 ms 48216 KB Output is correct
5 Correct 874 ms 24544 KB Output is correct
6 Correct 1192 ms 48484 KB Output is correct
7 Correct 867 ms 33396 KB Output is correct
8 Correct 1008 ms 48256 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Incorrect 2 ms 208 KB Output isn't correct
14 Halted 0 ms 0 KB -