제출 #569023

#제출 시각아이디문제언어결과실행 시간메모리
569023hibiki밀림 점프 (APIO21_jumps)C++11
48 / 100
1268 ms93488 KiB
#include "jumps.h" #include<bits/stdc++.h> using namespace std; #define all(x) x.begin(),x.end() #define sz(x) (int)x.size() #define pb push_back #define f first #define s second int n,h[200005]; int bk[200005][20],ft[200005][20]; vector<int> jp[200005]; void monotone_q_and_lds() { for(int i = 0; i < n; i++) bk[i][0] = i; memset(ft,-1,sizeof(ft)); stack<int> s; for(int i = 0; i < n; i++) { if(s.size()) while(!s.empty() && h[s.top()] < h[i]) { // s top go right that is i jp[s.top()].pb(i); ft[s.top()][0] = i; s.pop(); } if(!s.empty()) { // i go left that is s top jp[i].pb(s.top()); bk[i][0] = s.top(); } s.push(i); } } int spa[2][200005][20]; void gen_spa() { memset(spa,-1,sizeof(spa)); for(int i = 0; i < n; i++) { if(sz(jp[i]) > 0) spa[0][i][0] = jp[i][0]; if(sz(jp[i]) > 1) spa[1][i][0] = jp[i][1]; } for(int j = 1; j < 20; j++) { for(int i = 0; i < n; i++) { if(spa[0][i][j - 1] != -1) spa[0][i][j] = spa[0][spa[0][i][j - 1]][j - 1]; if(spa[1][i][j - 1] != -1) spa[1][i][j] = spa[1][spa[1][i][j - 1]][j - 1]; bk[i][j] = bk[bk[i][j - 1]][j - 1]; if(ft[i][j - 1] != -1) ft[i][j] = ft[ft[i][j - 1]][j - 1]; } } } int rmq[200005][20]; int pre_len[200005]; void gen_rmq() { memset(rmq,0,sizeof(rmq)); for(int i = 0; i < n; i++) rmq[i][0] = h[i]; for(int j = 1; j < 20; j++) { for(int i = 0; i < n; i++) { if(i + (1 << j) - 1 >= n) continue; int mid = i + (1 << (j - 1)); rmq[i][j] = max(rmq[i][j - 1], rmq[mid][j - 1]); } } pre_len[1] = 0; for(int i = 2; i < 200005; i++) { pre_len[i] = pre_len[i - 1]; if(i == (1 << (pre_len[i] + 1))) pre_len[i]++; } } void init(int N, vector<int> H) { // input n = N; for(int i = 0; i < n; i++) h[i] = H[i]; // jump monotone_q_and_lds(); for(int i = 0; i < n; i++) sort(all(jp[i]), [&](const int &x, const int &y) { return h[x] < h[y]; }); // jump sparse table gen_spa(); // rmq gen_rmq(); } int qu_rmq(int l,int r) { int qu_sz = pre_len[r - l + 1]; int mid = r - (1 << qu_sz) + 1; return max(rmq[l][qu_sz], rmq[mid][qu_sz]); } int qu_mx_s(int l,int r,int mx) { int ret = r; for(int j = 19; j >=0; j--) { if(l <= bk[ret][j] && h[bk[ret][j]] < mx) ret = bk[ret][j]; } return ret; } int qu_mn_step(int s,int l,int r,int mx) { int nw = s; int ret = 0; for(int j = 19; j >= 0; j--) { if(spa[1][nw][j] == -1) continue; if(spa[0][nw][j] < l && spa[1][nw][j] < l && h[spa[1][nw][j]] < mx) nw = spa[1][nw][j], ret += (1 << j); } for(int j = 19; j >= 0; j--) { if(ft[nw][j] == -1) continue; if(ft[nw][j] < l && h[ft[nw][j]] < mx) nw = ft[nw][j], ret += (1 << j); } if(ft[nw][0] < l || ft[nw][0] > r ) return -1; return ret + 1; } int minimum_jumps(int A, int B, int C, int D) { int mx = qu_rmq(C, D); int s = qu_mx_s(A, B, mx); return qu_mn_step(s, C, D, mx); }
#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...