Submission #1212407

#TimeUsernameProblemLanguageResultExecution timeMemory
1212407ProtonDecay314밀림 점프 (APIO21_jumps)C++20
48 / 100
816 ms135888 KiB
#include <bits/stdc++.h> #include "jumps.h" using namespace std; typedef long long ll; typedef vector<ll> vll; typedef vector<vll> vvll; typedef pair<ll, ll> pll; typedef vector<pll> vpll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> pi; typedef vector<pi> vpi; typedef vector<bool> vb; #define INF(dt) numeric_limits<dt>::max() #define NINF(dt) numeric_limits<dt>::min() #define pb push_back /* yeah i could've used a set... but i'm just coding a segtree because vibes :D */ struct Tree { Tree *lt, *rt; int l, r; int mn1, mx1; Tree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), mn1(INF(int)), mx1(NINF(int)) {}; void combine() { mn1 = min(lt->mn1, rt->mn1); mx1 = max(lt->mx1, rt->mx1); } void build(const vb& a) { if(l == r) { if(a[l]) { mn1 = mx1 = l; } return; } int m = (l + r) >> 1; lt = new Tree(l, m); rt = new Tree(m + 1, r); lt->build(a); rt->build(a); combine(); } int qmin(int ql, int qr) { if(ql > r || qr < l) return INF(int); if(ql == l && qr == r) return mn1; int m = (l + r) >> 1; return min(lt->qmin(ql, min(qr, m)), rt->qmin(max(ql, m + 1), qr)); } int qmax(int ql, int qr) { if(ql > r || qr < l) return NINF(int); if(ql == l && qr == r) return mx1; int m = (l + r) >> 1; return max(lt->qmax(ql, min(qr, m)), rt->qmax(max(ql, m + 1), qr)); } void upd(int i, bool nv) { if(l == r) { if(nv) mn1 = mx1 = l; else { mn1 = INF(int); mx1 = NINF(int); } return; } int m = (l + r) >> 1; if(i <= m) lt->upd(i, nv); else rt->upd(i, nv); combine(); } }; struct MaxTree { MaxTree *lt, *rt; int l, r, v; MaxTree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v(NINF(int)) {}; void combine() { v = max(lt->v, rt->v); } void build(const vi& a) { if(l == r) { v = a[l]; return; } int m = (l + r) >> 1; lt = new MaxTree(l, m); rt = new MaxTree(m + 1, r); lt->build(a); rt->build(a); combine(); } int qry(int ql, int qr) { if(ql > r || qr < l) return NINF(int); if(ql == l && qr == r) return v; int m = (l + r) >> 1; return max(lt->qry(ql, min(qr, m)), rt->qry(max(ql, m + 1), qr)); } }; vi g_lptr; vi g_rptr; void print_vec(const vi& v) { for(int vv : v) cerr << vv << " "; cerr << endl; } struct PICK_STRATEGY { const static int HEAVY = 0, LIGHT = 1, LEFT = 2, RIGHT = 3; }; const int MAX_JUMP = 20; vvi compute_jump_pointers(const vi& lptr, const vi& rptr, const vpi& node_order, const vi& h, int strategy) { int n = lptr.size(); vvi jump(n, vi(MAX_JUMP, -1)); // Initialize jump pointers for(int i = 0; i < n; i++) { int next_ptr = -1; switch(strategy) { default: case PICK_STRATEGY::HEAVY: { if(lptr[i] == NINF(int)) { next_ptr = (rptr[i] == INF(int) ? -1 : rptr[i]); } else if(rptr[i] == INF(int)) { next_ptr = lptr[i]; } else if(h[lptr[i]] > h[rptr[i]]) { next_ptr = lptr[i]; } else { next_ptr = rptr[i]; } } break; case PICK_STRATEGY::LIGHT: { if(lptr[i] == NINF(int)) { next_ptr = (rptr[i] == INF(int) ? -1 : rptr[i]); } else if(rptr[i] == INF(int)) { next_ptr = lptr[i]; } else if(h[lptr[i]] > h[rptr[i]]) { next_ptr = rptr[i]; } else { next_ptr = lptr[i]; } } break; case PICK_STRATEGY::LEFT: { next_ptr = (lptr[i] == NINF(int) ? -1 : lptr[i]); } break; case PICK_STRATEGY::RIGHT: { next_ptr = (rptr[i] == INF(int) ? -1 : rptr[i]); } break; } jump[i][0] = next_ptr; } for(int i = 0; i < n; i++) { int ci = node_order[i].second; for(int j = 1; j < MAX_JUMP; j++) { if(jump[ci][j - 1] == -1) break; jump[ci][j] = jump[jump[ci][j - 1]][j - 1]; } } return jump; } vvi heavy_ptrs; vvi left_ptrs; vvi right_ptrs; MaxTree* g_tr; vi g_h; void init(int N, vi H) { // computing left/right pointers vpi h_ind_pairs_right_order; vpi h_ind_pairs_left_order; vi lptr(N, -1); vi rptr(N, -1); for(int i = 0 ; i < N; i++) { h_ind_pairs_right_order.pb({H[i], i}); h_ind_pairs_left_order.pb({H[i], i}); } sort(h_ind_pairs_right_order.begin(), h_ind_pairs_right_order.end(), [](pi a, pi b) {return a.first > b.first || (a.first == b.first && a.second < b.second);}); sort(h_ind_pairs_left_order.begin(), h_ind_pairs_left_order.end(), [](pi a, pi b) {return a.first > b.first || (a.first == b.first && a.second > b.second);}); Tree* tr_right = new Tree(0, N - 1); Tree* tr_left = new Tree(0, N - 1); vb all_false(N, false); tr_right->build(all_false); tr_left->build(all_false); for(int i = 0 ; i < N; i++) { rptr[h_ind_pairs_right_order[i].second] = tr_right->qmin(h_ind_pairs_right_order[i].second + 1, N - 1); lptr[h_ind_pairs_left_order[i].second] = tr_left->qmax(0, h_ind_pairs_left_order[i].second - 1); tr_right->upd(h_ind_pairs_right_order[i].second, true); tr_left->upd(h_ind_pairs_left_order[i].second, true); } g_lptr = lptr; g_rptr = rptr; /* computing jump pointers you will need: (1) heavy jump pointers (2) light jump pointers (nvm no need for this) (3) left jump pointers (4) right jump pointers */ heavy_ptrs = compute_jump_pointers(lptr, rptr, h_ind_pairs_left_order, H, PICK_STRATEGY::HEAVY); left_ptrs = compute_jump_pointers(lptr, rptr, h_ind_pairs_left_order, H, PICK_STRATEGY::LEFT); right_ptrs = compute_jump_pointers(lptr, rptr, h_ind_pairs_left_order, H, PICK_STRATEGY::RIGHT); g_tr = new MaxTree(0, N - 1); g_tr->build(H); g_h = H; } int p2p_minjumps(int s, int C) { int num_jumps = 0; int ci = s; // Jump along heavy edges for(int i = MAX_JUMP - 1; i >= 0; i--) { if(heavy_ptrs[ci][i] != -1 && g_h[heavy_ptrs[ci][i]] < g_h[C]) { // if we can jump, jump num_jumps |= 1 << i; ci = heavy_ptrs[ci][i]; } } // Jump to the right for(int i = MAX_JUMP - 1; i >= 0; i--) { if(right_ptrs[ci][i] != -1 && right_ptrs[ci][i] < C) { // if we can jump, jump num_jumps += 1 << i; ci = right_ptrs[ci][i]; } } return num_jumps + 1; } int minimum_jumps(int A, int B, int C, int D) { // Binary jumping // The idea is to find the optimal starting point in [A, B] // Move as far to the right as you possibly can (find the peak) int ce = C; for(int i = MAX_JUMP - 1; i >= 0; i--) { if(right_ptrs[ce][i] != -1 && right_ptrs[ce][i] <= D) { ce = right_ptrs[ce][i]; } } if(g_tr->qry(B, ce - 1) >= g_h[ce]) return -1; // Move as far to the left as you possibly can int cs = B; for(int i = MAX_JUMP - 1; i >= 0; i--) { if(left_ptrs[cs][i] != -1 && g_h[left_ptrs[cs][i]] < g_h[ce] && left_ptrs[cs][i] >= A) { cs = left_ptrs[cs][i]; } } return p2p_minjumps(cs, C); }
#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...