제출 #1112802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112802		PagodePaiva	밀림 점프 (APIO21_jumps)	C++17	48 / 100	2520 ms	85688 KiB

jumps

    #include<bits/stdc++.h>
    #include "jumps.h"
    #define fr first
    #define sc second
     
    using namespace std;
     
    const int N = 200010;
    const int LOGN = 20;
     
    struct Segtree{
      pair <int, int> tree[4*N];
      pair <int, int> join(pair <int, int> a, pair <int, int> b){
        return {min(a.fr, b.fr), max(a.sc, b.sc)};
      }
      void build(int node, int l, int r){
        if(l == r){
          tree[node] = {1e9, 0};
          return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
      }
      void update(int node, int l, int r, int pos, int val){
        if(l == r){
          tree[node] = {l, l};
          return;
        }
        int mid = (l+r)/2;
        if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
        else update(2*node+1, mid+1, r, pos, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
      }
      pair <int, int> query(int node, int l, int r, int tl, int tr){
        if(l > tr or tl > r) return {1e9, -1};
        if(l <= tl and tr <= r) return tree[node];
        int mid = (tl+tr)/2;
        return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
      }
    } seg;
     
    struct Segtree2{
      pair <int, int> tree[4*N];
      pair <int, int> join(pair <int, int> a, pair <int, int> b){
        if(a.fr > b.fr) return a;
        return b;
      }
      void build(int node, int l, int r){
        if(l == r){
          tree[node] = {0, l};
          return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
      }
      void update(int node, int l, int r, int pos, int val){
        if(l == r){
          tree[node] = {val, l};
          return;
        }
        int mid = (l+r)/2;
        if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
        else update(2*node+1, mid+1, r, pos, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
      }
      pair <int, int> query(int node, int l, int r, int tl, int tr){
        if(l > tr or tl > r) return {-1, -1};
        if(l <= tl and tr <= r) return tree[node];
        int mid = (tl+tr)/2;
        return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
      }
    } seg2;
     
    int l[N], r[N];
    int lc[N], rc[N];
    int pai[N][LOGN], pai2[N][LOGN];
    int tin[N], tout[N];
    vector <int> g[N];
    int n;
    int tmm;
    int il[N], ir[N];
    int alt[N];
     
    void dfs(int v, int p){
      pai2[v][0] = p;
      tin[v] = tmm;
      tmm++;
      for(auto x : g[v]){
        if(x == p) continue;
        alt[x] = alt[v]+1;
        dfs(x, v);
      }
      tout[v] = tmm;
      tmm++;
    }
     
    void construct(int l = 1, int r = n){
      int t = seg2.query(1, l, r, 1, n).sc;
      il[t] = l;
      ir[t] = r;
      if(seg2.query(1, l, t-1, 1, n).first > 0){
        lc[t] = seg2.query(1, l, t-1, 1, n).sc;
        construct(l, t-1);
      }
      if(seg2.query(1, t+1, r, 1, n).fr > 0){
        rc[t] = seg2.query(1, t+1, r, 1, n).sc;
        construct(t+1, r);
      }
    }
     
    void init(int N, vector<int> h) {
      n = N;
      vector <pair <int, int>> v;
      for(int i = 0;i < n;i++){
        v.push_back({h[i], i+1});
      }
      sort(v.begin(), v.end());
      reverse(v.begin(), v.end());
      seg.build(1, 1, n);
      for(auto [val, pos] : v){
        l[pos] = r[pos] = -1;
        if(seg.query(1, 1, pos-1, 1, n).sc > 0) l[pos] = seg.query(1, 1, pos-1, 1, n).sc;
        if(seg.query(1, pos+1, n, 1, n).fr < 1e9) r[pos] = seg.query(1, pos+1, n, 1, n).fr;
        seg.update(1,1, n, pos, pos);
      }
      reverse(v.begin(), v.end());
      seg2.build(1, 1, n);
      for(auto [val, pos] : v){
        lc[pos] = rc[pos] = -1;
        seg2.update(1, 1, n, pos, val);
      }
      construct();
      int raiz = 0;
      for(int i = 1;i <= n;i++){
        if(h[i-1] == n) raiz = i;
        if(lc[i] != -1){
          g[lc[i]].push_back(i);
          g[i].push_back(lc[i]);
        }
        if(rc[i] != -1) {
          g[rc[i]].push_back(i);
          g[i].push_back(rc[i]);
        }
        //cout << lc[i] << ' ' << rc[i] << '\n';
      }
      tmm = 1;
      g[raiz].push_back(0);
      g[0].push_back(raiz);
      pai[raiz][0] = 0;
      pai2[raiz][0] = 0;
      dfs(0, 0);
      for(int i = 1;i <= n;i++){
        if(l[i] == -1 and r[i] == -1) {
          continue;
        }
        if(l[i] == -1) pai[i][0] = r[i];
        else if(r[i] == -1) pai[i][0] = l[i];
        else{
          int u = l[i], v = r[i];
          if(tin[u] <= tin[v] and tout[v] <= tout[u]){
            pai[i][0] = u;
          }
          else{
            pai[i][0] = v;
          }
        }
      }  
      for(int bit = 1;bit < LOGN;bit++){
        for(int i = 1;i <= n;i++){
          pai[i][bit] = pai[pai[i][bit-1]][bit-1];
          pai2[i][bit] = pai2[pai2[i][bit-1]][bit-1];
        }
      }
      return;
    }
     
    int check(int u, int v){
      return (tin[v] <= tin[u] and tout[u] <= tout[v]);
    }
     
    vector <int> choose(int a, int b, int c){
      a = max(a, il[c]);
      vector <int> ans;
      while(a <= b){
        int t = seg2.query(1, a,b, 1, n).sc;
        ans.push_back(t);
        a = ir[t]+1;
      }
      return ans;
    }
     
    int minimum_jumps(int a, int b, int c, int d) {
      // a=b and c = d
      a++;
      b++;
      c++;
      d++;
      vector <int> st = choose(a, b, c);
      int resp = 1e9;
      for(auto u : st){
        int v = c;
        if(!check(u, v)){
          continue;
        }
        int res = 0;
        for(int bit = LOGN-1;bit >= 0;bit--){
          if(check(pai[u][bit], v)){
            u = pai[u][bit];
            int t = (1<<bit);
            res += t;
          }
        }
        for(int bit = LOGN-1;bit >= 0;bit--){
          if(check(pai2[u][bit], v)){
            u = pai2[u][bit];
            int t = (1<<bit);
            res += t;
          }
        }
        resp = min(res, resp);
      }
      return (resp == 1e9 ? -1 : resp);
    }

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 0 / 19