oj.uz

Submission #649905

# Submission time Handle Problem Language Result Execution time Memory
649905 2022-10-11T15:06:24 Z ToroTN Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1301 ms 84648 KB 
#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#include <vector>
int n,h[200005],l[200005][25],r[200005][25],a,b,c,d,mx,node,cnt;
int low[200005][25],high[200005][25],seg[800005],ans;
stack<pair<int,int> > stk;
void build(int tree,int st,int ed)
{
    int md=(st+ed)/2;
    if(st==ed)
    {
        seg[tree]=h[st];
        return;
    }
    build(2*tree,st,md);
    build(2*tree+1,md+1,ed);
    seg[tree]=max(seg[2*tree],seg[2*tree+1]);
}
int query(int tree,int st,int ed,int l,int r)
{
    int md=(st+ed)/2;
    if(st>r||ed<l)return -1e9;
    if(st>=l&&ed<=r)return seg[tree];
    return max(query(2*tree,st,md,l,r),query(2*tree+1,md+1,ed,l,r));
}
void debug(int tree,int st,int ed)
{
    int md=(st+ed)/2;
    if(st==ed)
    {
        printf("%d %d %d %d\n",tree,st,ed,seg[tree]);
        return;
    }
    debug(2*tree,st,md);
    debug(2*tree+1,md+1,ed);
    printf("%d %d %d %d\n",tree,st,ed,seg[tree]);
}
void init(int N, std::vector<int> H) {
    n=N;
    for(int i=1;i<=n;i++)
    {
        h[i]=H[i-1];
    }
    build(1,1,n);
    //debug(1,1,n);
    for(int i=1;i<=n;i++)
    {
        while(!stk.empty())
        {
            if(stk.top().X>h[i])
            {
                break;
            }else
            {
                r[stk.top().Y][0]=i;
                stk.pop();
            }
        }
        stk.push({h[i],i});
    }
    while(!stk.empty())
    {
        stk.pop();
    }
    for(int i=n;i>=1;i--)
    {
        while(!stk.empty())
        {
            if(stk.top().X>h[i])
            {
                break;
            }else
            {
                l[stk.top().Y][0]=i;
                stk.pop();
            }
        }
        stk.push({h[i],i});
    }
    while(!stk.empty())
    {
        stk.pop();
    }
    for(int i=1;i<=n;i++)
    {
        if(l[i][0]!=0&&r[i][0]!=0)
        {
            low[i][0]=l[i][0];
            high[i][0]=r[i][0];
            if(h[l[i][0]]>h[r[i][0]])swap(low[i][0],high[i][0]);
        }else if(l[i][0]!=0||r[i][0]!=0)
        {
            low[i][0]=high[i][0]=max(l[i][0],r[i][0]);
        }
    }
    for(int i=1;i<=20;i++)
    {
        for(int j=1;j<=n;j++)
        {
            l[j][i]=l[l[j][i-1]][i-1];
            r[j][i]=r[r[j][i-1]][i-1];
            low[j][i]=low[low[j][i-1]][i-1];
            high[j][i]=high[high[j][i-1]][i-1];
        }
    }
    // for(int j=0;j<=20;j++)
    // {
    //     printf("%d\n",j);
    //     for(int i=1;i<=n;i++)
    //     {
    //         printf("%d ",r[i][j]);
    //     }
    //     printf("\n");
    //     for(int i=1;i<=n;i++)
    //     {
    //         printf("%d ",l[i][j]);
    //     }
    //     printf("\n");
    //     for(int i=1;i<=n;i++)
    //     {
    //         printf("%d ",low[i][j]);
    //     }
    //     printf("\n");
    //     for(int i=1;i<=n;i++)
    //     {
    //         printf("%d ",high[i][j]);
    //     }
    //     printf("\n");
    // }
}
int minimum_jumps(int A, int B, int C, int D) {
    a=A+1;
    b=B+1;
    c=C+1;
    d=D+1;
    mx=query(1,1,n,c,d);
    node=b;
    if(r[node][0]>=c&&r[node][0]<=d)return 1;
    //printf("mx=%d\n",mx);
    //printf("%d\n",node);
    for(int i=20;i>=0;i--)
    {
        if(l[node][i]!=0)
        {
            if(h[l[node][i]]<mx&&l[node][i]>=a)
            {
                node=l[node][i];
            }
        }
    }
    //printf("%d %d\n",node,ans);
    ans=0;
    if(r[node][0]>=c&&r[node][0]<=d)return ans+1;
    for(int i=20;i>=0;i--)
    {
        if(high[node][i]!=0)
        {
            //printf("high=%d %d\n",i,high[node][i]);
            if(h[high[node][i]]<mx&&high[node][i]<c&&r[high[node][i]][0]<c&&r[high[node][i]][0]!=0)
            {
                node=high[node][i];
                ans+=(1<<i);
            }
        }
    }
    //printf("%d %d\n",node,ans);
    node=high[node][0];
    ans+=1;
    if(r[node][0]>=c&&r[node][0]<=d)return ans+1;
    for(int i=20;i>=0;i--)
    {
        if(low[node][i]!=0)
        {
            if(h[low[node][i]]<mx&&low[node][i]<c)
            {
                node=low[node][i];
                ans+=(1<<i);
            }
        }
    }
    //printf("%d %d\n",node,ans);
    ans+=1;
    node=r[node][0];
    if(node>=c&&node<=d)
    {
        return ans;
    }
    return -1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 248 ms 67856 KB Output is correct
4 Correct 1152 ms 84628 KB Output is correct
5 Correct 875 ms 42788 KB Output is correct
6 Correct 1301 ms 84624 KB Output is correct
7 Correct 984 ms 58440 KB Output is correct
8 Correct 1128 ms 84552 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Incorrect 3 ms 336 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 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Incorrect 3 ms 336 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 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 131 ms 67232 KB Output is correct
6 Correct 157 ms 82976 KB Output is correct
7 Correct 83 ms 42636 KB Output is correct
8 Correct 161 ms 82876 KB Output is correct
9 Correct 24 ms 12624 KB Output is correct
10 Correct 163 ms 82876 KB Output is correct
11 Correct 166 ms 84648 KB Output is correct
12 Incorrect 160 ms 83992 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Incorrect 302 ms 38180 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 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 248 ms 67856 KB Output is correct
4 Correct 1152 ms 84628 KB Output is correct
5 Correct 875 ms 42788 KB Output is correct
6 Correct 1301 ms 84624 KB Output is correct
7 Correct 984 ms 58440 KB Output is correct
8 Correct 1128 ms 84552 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Incorrect 3 ms 336 KB Output isn't correct
14 Halted 0 ms 0 KB -