Submission #442152

#TimeUsernameProblemLanguageResultExecution timeMemory
442152Haruto810198Rainforest Jumps (APIO21_jumps)C++17
44 / 100
1404 ms67764 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define double long double #define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d)) #define szof(x) ((int)(x).size()) #define vi vector<int> #define pii pair<int,int> #define F first #define S second #define pb push_back #define eb emplace_back #define mkp make_pair #define V st[cidx] #define LC st[cidx*2] #define RC st[cidx*2+1] #define lsb(x) ((x)&(-(x))) //const int INF = 2147483647; //const int LNF = INF*INF; const int INF = 1000000007; const int MOD = 1000000007; const int mod = 998244353; const double eps = 1e-12; //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") const int MAX = 200010; const int lgMAX = 20; int n; int h[MAX]; int edge_l[MAX], edge_r[MAX]; int anc_l[MAX][lgMAX]; int anc_hi[MAX][lgMAX], anc_lo[MAX][lgMAX]; int Max[MAX][lgMAX]; int dest_Max; int query_Max(int L, int R){ /// [L, R] int len = R - L + 1; int lglen = __lg(len); return max(Max[L][lglen], Max[R - (1<<lglen) + 1][lglen]); } int get_start(int A, int B){ int ret = B; for(int j=lgMAX-1; j>=0; j--){ if( anc_l[ret][j] != INF and h[anc_l[ret][j]] < dest_Max and anc_l[ret][j] >= A ){ ret = anc_l[ret][j]; } } return ret; } pii jump_hi(int v){ int ret = 0; for(int j=lgMAX-1; j>=0; j--){ if( anc_hi[v][j] != INF and h[anc_hi[v][j]] <= dest_Max ){ v = anc_hi[v][j]; ret += (1<<j); } } return mkp(v, ret); } int jump_lo(int v){ int ret = 0; for(int j=lgMAX-1; j>=0; j--){ if( anc_lo[v][j] != INF and h[anc_lo[v][j]] <= dest_Max ){ v = anc_lo[v][j]; ret += (1<<j); } } if( h[v] > dest_Max ){ ret = INF; } if( h[v] < dest_Max and ( anc_lo[v][0] == INF or h[anc_lo[v][0]] > dest_Max ) ){ ret = INF; } return ret; } void init(int N, vi H){ /// input n = N; FOR(i, 0, n-1, 1){ h[i] = H[i]; } /// monotonic stack FOR(i, 0, n-1, 1){ edge_l[i] = INF; /// INF -> no edge edge_r[i] = INF; } vi stk; FOR(i, 0, n-1, 1){ while(!stk.empty() and h[stk.back()] < h[i]){ stk.pop_back(); } if(!stk.empty()){ edge_l[i] = stk.back(); } stk.pb(i); } stk.clear(); for(int i=n-1; i>=0; i--){ while(!stk.empty() and h[stk.back()] < h[i]){ stk.pop_back(); } if(!stk.empty()){ edge_r[i] = stk.back(); } stk.pb(i); } /// 2^k-th ancestor FOR(i, 0, n-1, 1){ if(edge_l[i]==INF and edge_r[i]==INF){ anc_hi[i][0] = INF; anc_lo[i][0] = INF; } else if(edge_l[i]==INF or edge_r[i]==INF){ anc_hi[i][0] = INF; anc_lo[i][0] = min(edge_l[i], edge_r[i]); } else{ anc_hi[i][0] = (h[edge_l[i]] > h[edge_r[i]]) ? edge_l[i] : edge_r[i]; anc_lo[i][0] = (h[edge_l[i]] < h[edge_r[i]]) ? edge_l[i] : edge_r[i]; } anc_l [i][0] = edge_l[i]; } FOR(j, 1, lgMAX-1, 1){ FOR(i, 0, n-1, 1){ anc_hi[i][j] = (anc_hi[i][j-1]!=INF) ? anc_hi[ anc_hi[i][j-1] ][j-1] : INF; anc_lo[i][j] = (anc_lo[i][j-1]!=INF) ? anc_lo[ anc_lo[i][j-1] ][j-1] : INF; anc_l [i][j] = (anc_l [i][j-1]!=INF) ? anc_l [ anc_l [i][j-1] ][j-1] : INF; } } /// sparse table for Max query FOR(i, 0, n-1, 1){ Max[i][0] = h[i]; } FOR(j, 1, lgMAX-1, 1){ FOR(i, 0, n-1, 1){ if(i + (1<<j-1) <= n-1){ Max[i][j] = max(Max[i][j-1], Max[i + (1<<j-1)][j-1]); } else{ Max[i][j] = Max[i][j-1]; } } } } int minimum_jumps(int A, int B, int C, int D){ dest_Max = query_Max(C, D); //cerr<<"dest_Max = "<<dest_Max<<endl; int start = get_start(A, B); //cerr<<"start = "<<start<<endl; int v = start, res; pii tmp = jump_hi(start); v = tmp.F; res = tmp.S; //cerr<<"jump_hi : v = "<<tmp.F<<", res += "<<tmp.S<<endl; res += jump_lo(v); //cerr<<"jump_lo : res += "<<jump_lo(v)<<endl; //cerr<<"res = "<<res<<endl; if(res < INF){ return res; } else{ return -1; } } /* signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); init(7, {3, 2, 1, 6, 4, 5, 7}); cerr<<minimum_jumps(4, 4, 6, 6)<<endl; /// 2 cerr<<minimum_jumps(1, 3, 5, 6)<<endl; /// 1 cerr<<minimum_jumps(0, 1, 2, 2)<<endl; /// -1 return 0; } */

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:164:25: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  164 |             if(i + (1<<j-1) <= n-1){
      |                        ~^~
jumps.cpp:165:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  165 |                 Max[i][j] = max(Max[i][j-1], Max[i + (1<<j-1)][j-1]);
      |                                                          ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...