oj.uz

Submission #734058

# Submission time Handle Problem Language Result Execution time Memory
734058 2023-05-01T15:25:13 Z WKYH Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1093 ms 66108 KB 
#include<bits/stdc++.h>
#define qc ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rt return
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vecin(a) for(auto &d:a)cin>>d;
typedef long long int ll;
const long long mod=1e9+7;
const int int_inf=2147483647;
const long long int ll_inf=9223372036854775807;
const int alp_up=64;
const int alp_lw=96;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
using namespace std;
ll gcd(ll a,ll b){if(b==0)rt a;rt gcd(b,a%b);}
ll lcm(ll a,ll b){rt a/gcd(a,b)*b;}
void setIO(string name)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}

//*
int n;
vector<int>h;
vector<vector<int>>l,r,low,hgh;
void init(int N,vector<int>H)
{
    n=N;h=H;
    l.resize(20,vector<int>(n,-1));
    r.resize(20,vector<int>(n,-1));
    low.resize(20,vector<int>(n,-1));
    hgh.resize(20,vector<int>(n,-1));
    // monotonic stack for l and r
        // -1 means no target
    stack<int>s;
    for(int i=0;i<n;i++)
    {
        while(!s.empty()&&h[s.top()]<h[i])s.pop();
        if(!s.empty())l[0][i]=s.top();
        s.push(i);
    }
    while(!s.empty())s.pop();
    for(int i=n-1;i>=0;i--)
    {
        while(!s.empty()&&h[s.top()]<h[i])s.pop();
        if(!s.empty())r[0][i]=s.top();
        s.push(i);
    }
    // sparse table for l and r
    for(int i=1;i<20;i++){
        for(int j=0;j<n;j++){
            if(l[i-1][j]!=-1)l[i][j]=l[i-1][l[i-1][j]];
            if(r[i-1][j]!=-1)r[i][j]=r[i-1][r[i-1][j]];
        }
    }
    // sparse table for low and hgh
        // using dynamic programming
    for(int i=0;i<n;i++){
        if(l[0][i]==-1)hgh[0][i]=r[0][i];
        else if(r[0][i]==-1)hgh[0][i]=l[0][i];
        else if(h[l[0][i]]>h[r[0][i]]){
            hgh[0][i]=l[0][i];
            low[0][i]=r[0][i];
        }
        else{
            hgh[0][i]=r[0][i];
            low[0][i]=l[0][i];
        }
    }
    for(int i=1;i<20;i++){
        for(int j=0;j<n;j++){
            if(low[i-1][j]!=-1)low[i][j]=low[i-1][low[i-1][j]];
            if(hgh[i-1][j]!=-1)hgh[i][j]=hgh[i-1][hgh[i-1][j]];
        }
    }
    //for(auto c:l)cout<<c<<" ";cout<<"\n";
    //for(auto c:r)cout<<c<<" ";cout<<"\n";
    //for(auto c:tall){for(auto d:c)cout<<d<<" ";cout<<"\n";}
}
int reachable(int cur,int c,int d,int ans) // #jump from cur
{
    if(c<=low[0][cur]&&low[0][cur]<=d)rt ans+1;
    if(c<=hgh[0][cur]&&hgh[0][cur]<=d)rt ans+1;

    for(int i=19;i>=0;i--){
        if(hgh[i][cur]==-1)continue;
        if(hgh[i][cur]>=c)continue;
        rt reachable(hgh[i][cur],c,d,ans+(1<<i));
    }
    for(int i=19;i>=0;i--){
        if(low[i][cur]==-1)continue;
        if(low[i][cur]>=c)continue;
        rt reachable(low[i][cur],c,d,ans+(1<<i));
    }
    rt -1;
}
int tallest(int a,int cur,int lim) // tallest tree in [a,cur] not higher than lim
{
    for(int i=19;i>=0;i--){
        if(l[i][cur]==-1)continue;
        if(h[l[i][cur]]>lim)continue;
        if(l[i][cur]<a)continue;
        rt tallest(a,l[i][cur],lim);
    }
    rt cur;
}
int minimum_jumps(int a,int b,int c,int d)
{
    int t_dest=tallest(c,d,n);
    int t_strt=tallest(a,b,h[t_dest]);
    rt reachable(t_strt,c,d,0);
}

int xmain()
{
    init(7, {3, 2, 1, 6, 4, 5, 7});
    cout<<minimum_jumps(4, 4, 6, 6)<<" "<<minimum_jumps(1, 3, 5, 6)<<" "<<minimum_jumps(0, 1, 2, 2);
    rt 0;
}
/*/

vector<int> construct_permutation(ll k)
{
    k-=2;
    vector<int>ans;
    for(int i=k;i>=0;i--){
        ans.push_back(i);
    }
    rt ans;
}
int smain()
{

}

//*/

Compilation message

jumps.cpp: In function 'void setIO(std::string)':
jumps.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.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 175 ms 52636 KB Output is correct
4 Correct 1054 ms 66104 KB Output is correct
5 Correct 951 ms 33420 KB Output is correct
6 Correct 1093 ms 66104 KB Output is correct
7 Correct 775 ms 45292 KB Output is correct
8 Correct 803 ms 66080 KB Output is correct

Subtask #2
0 / 8.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 1 ms 208 KB Output is correct
4 Correct 0 ms 208 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 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 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 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 0 ms 208 KB Output is correct
5 Correct 64 ms 53144 KB Output is correct
6 Correct 72 ms 66108 KB Output is correct
7 Correct 35 ms 33948 KB Output is correct
8 Correct 70 ms 66060 KB Output is correct
9 Correct 12 ms 10148 KB Output is correct
10 Correct 72 ms 66064 KB Output is correct
11 Correct 72 ms 66056 KB Output is correct
12 Incorrect 74 ms 65988 KB Output isn't correct
13 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 173 ms 30344 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 173 ms 30344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.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 175 ms 52636 KB Output is correct
4 Correct 1054 ms 66104 KB Output is correct
5 Correct 951 ms 33420 KB Output is correct
6 Correct 1093 ms 66104 KB Output is correct
7 Correct 775 ms 45292 KB Output is correct
8 Correct 803 ms 66080 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Incorrect 2 ms 208 KB Output isn't correct
14 Halted 0 ms 0 KB -