oj.uz

Submission #657699

# Submission time Handle Problem Language Result Execution time Memory
657699 2022-11-10T17:44:18 Z activedeltorre Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 988 ms 10684 KB 
#include "jumps.h"

#include <fstream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
//ifstream cin("a.in");
//ofstream cout("a.out");
stack <int>st;
int v[200005];
int dpst[200005];
int dpdr[200005];
int nextst[200005];
int nextdr[200005];
int aint[3][600005];
int n;
int querry(int node,int st,int dr,int qst,int qdr,int tip)
{
    if(st>qdr || qst>dr)
    {
        return 10000000;
    }
    else if(qst<=st && dr<=qdr)
    {
        return aint[tip][node];
    }
    else if(st!=dr)
    {
        int mij=(st+dr)/2,val1,val2;
        val1=querry(node*2,st,mij,qst,qdr,tip);
        val2=querry(node*2+1,mij+1,dr,qst,qdr,tip);
        return min(val1,val2);
    }
}
void build(int node,int st,int dr)
{
    if(st==dr)
    {
        aint[0][node]=dpst[st];
        aint[1][node]=dpdr[st];
        return;
    }
    if(st!=dr)
    {
        int mij=(st+dr)/2;
        build(node*2,st,mij);
        build(node*2+1,mij+1,dr);
        aint[0][node]=min(aint[0][node*2],aint[0][node*2+1]);
        aint[1][node]=min(aint[1][node*2],aint[1][node*2+1]);
        return;
    }
}
void init(int N, vector<int> H)
{
    int i;
    n=N;
        //cout<<"pula";
    for(i=1; i<=n; i++)
    {
        v[i]=H[i-1];
    }
    v[0]=1e8;
    st.push(0);
    dpst[0]=0;
    for(i=1; i<=n; i++)
    {
        while(v[i]>v[st.top()])
        {
            st.pop();
        }
        nextst[i]=st.top();
        dpst[i]=dpst[st.top()]+1;
        st.push(i);
    }
    while(st.size())
    {
        st.pop();
    }
    st.push(n+1);
    v[n+1]=1e8;
    dpdr[n+1]=0;
    for(i=n; i>=1; i--)
    {
        while(v[i]>v[st.top()])
        {
            st.pop();
        }
        nextdr[i]=st.top();
        dpdr[i]=dpdr[st.top()]+1;
        st.push(i);
    }
    build(1,1,n);
}
int minimum_jumps(int a, int b, int c, int d)
{
    int i,k,curr;
    a++;
    b++;
    c++;
    d++;
    if(a>b)
    {
        swap(a,b);
    }
    if(a<=c && b>=c)
    {
        return 0;
    }
    if(c<a)
    {
        if(nextdr[c]>a)
        {
            b=min(b,nextdr[c]-1);
            return querry(1,1,n,a,b,0)-dpst[c];
        }
        else
        {
            return -1;
        }
    }
    if(c>b)
    {
        if(nextst[c]<b)
        {
            a=max(a,nextst[c]+1);
            return querry(1,1,n,a,b,1)-dpdr[c];
        }
        else
        {
            return -1;
        }
    }
    return -1;
}
vector<int>vect;
/*int main ()
{
    int ne,i,q,a,b,c,d,x;
    cin>>ne>>q;
    for(i=1;i<=ne;i++)
    {
        cin>>x;
        vect.push_back(x);
    }
    init(ne,vect);
    for(i=1;i<=q;i++)
    {
        cin>>a>>b>>c>>d;
        cout<<minimum_jumps(a,b,c,d)<<'\n';
    }
    return 0;
}*/

Compilation message

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:97:9: warning: unused variable 'i' [-Wunused-variable]
   97 |     int i,k,curr;
      |         ^
jumps.cpp:97:11: warning: unused variable 'k' [-Wunused-variable]
   97 |     int i,k,curr;
      |           ^
jumps.cpp:97:13: warning: unused variable 'curr' [-Wunused-variable]
   97 |     int i,k,curr;
      |             ^~~~
jumps.cpp: In function 'int querry(int, int, int, int, int, int)':
jumps.cpp:35:1: warning: control reaches end of non-void function [-Wreturn-type]
   35 | }
      | ^

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 104 ms 9424 KB Output is correct
4 Correct 956 ms 10684 KB Output is correct
5 Correct 916 ms 5456 KB Output is correct
6 Correct 816 ms 10680 KB Output is correct
7 Correct 655 ms 8648 KB Output is correct
8 Correct 988 ms 10684 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 233 ms 4820 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 336 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 233 ms 4820 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 104 ms 9424 KB Output is correct
4 Correct 956 ms 10684 KB Output is correct
5 Correct 916 ms 5456 KB Output is correct
6 Correct 816 ms 10680 KB Output is correct
7 Correct 655 ms 8648 KB Output is correct
8 Correct 988 ms 10684 KB Output is correct
9 Incorrect 0 ms 208 KB Output isn't correct
10 Halted 0 ms 0 KB -