제출 #1256799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256799		nicolo_010	장애물 (IOI25_obstacles)	C++20	24 / 100	521 ms	139708 KiB

obstacles

#pragma GCC optimize("Ofast")
#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
#define cerr if(0) cerr

struct SegTree {
  v<int> tree;

  SegTree() {}

  SegTree(int n) {
    tree.assign(4*n, 1e9);
  }

  void build(int p, int l, int r, int i, int x) {
    if (l > i || r < i) return;
    if (l == r && r == i) {
      tree[p] = x;
    }
    else {
      build(2*p, l, (l+r)/2, i, x);
      build(2*p+1, (l+r)/2+1, r, i, x);
      tree[p] = min(tree[2*p], tree[2*p+1]);
    }
  }

  int query(int p, int l, int r, int i, int j) {
    if (l > j || r < i) return 1e9;
    if (i <= l && r <= j) return tree[p];
    else {
      int i1 = query(2*p, l, (l+r)/2, i, j);
      int i2 = query(2*p+1, (l+r)/2+1, r, i, j);
      return min(i1, i2);
    }
  }

  int find_first(int p, int l, int r, int ql, int x) {
    if (r < ql) return 1e9;
    if (tree[p] >= x) return 1e9;
    if (l == r) return l;
    int m = (l+r)/2;
    int ans = find_first(2*p, l, m, ql, x);
    if (ans == 1e9) {
      ans = find_first(2*p+1, m+1, r, ql, x);
    }
    return ans;
  }

  int find_last(int p, int l, int r, int qr, int x) {
    if (l > qr) return -1e9;
    if (tree[p] >= x) return -1e9;
    if (l == r) return l;

    int m = (l+r)/2;
    int ans = find_last(2*p+1, m+1, r, qr, x);
    if (ans == -1e9) {
      ans = find_last(2*p, l, m, qr, x);
    }
    return ans;
  }

};

struct DSU {
  v<int> par;
  v<int> L, R;
  DSU() {}

  DSU(int n) {
    par.assign(n, 0);
    L.resize(n);
    R.resize(n);
    rep(i, 0, n) {
      par[i] = i;
      L[i] = i;
      R[i] = i;
    }
  }

  int find(int n) {
    return (n == par[n] ? n : par[n] = find(par[n]));
  }

  void unite(int n1, int n2) {
    int p1 = find(n1);
    int p2 = find(n2);

    par[p1] = p2;
    L[p2] = min(L[p1], L[p2]);
    R[p2] = max(R[p1], R[p2]);
  }
};

struct Tree {
  int t;
  v<v<int>> lift;
  v<v<int>> path;
  v<v<pii>> adj;
  v<int> h;
  int n;

  void init(int _n, int _t) {
    n = _n;
    t = _t;
    adj.resize(n);
    h.assign(n, -1);
    lift.assign(n, v<int>(20));
    path.assign(n, v<int>(20));
  }

  //Si t es 0 entonces min, si t es 1 max 
  int join(int x, int y) {
    if (t == 1) {
      return max(x, y);
    }
    else return min(x, y);
  }

  void add(int a, int b, int w) {
    adj[a].push_back({b, w});
    adj[b].push_back({a, w});
  }

  void dfs(int n, int p=-1) {
    for (auto x : adj[n]) {
      if (x.first == p) continue;
      int u = x.first;
      int w = x.second;
      h[u] = h[n]+1;
      lift[u][0] = n;
      path[u][0] = w;
      dfs(x.first, n);
    }
  }

  void prepare(int r) {
    h[r] = 0;
    dfs(r);

    rep(j, 1, 20) {
      rep(i, 0, n) {
        lift[i][j] = lift[lift[i][j-1]][j-1];
        path[i][j] = join(path[i][j-1], path[lift[i][j-1]][j-1]);
      }
    }
  }

  //h[a] < h[b]
  int weight(int a, int b) {
    if (h[a] < h[b]) {
      swap(a, b);
    }
    int ans = (t ? -1e9 : 1e9);
    int diff = h[a] - h[b];
    rep(i, 0, 20) {
      if ((diff >> i) & 1) {
        ans = join(ans, path[a][i]);
        a = lift[a][i];
      }
    }
    cerr << a << " " << b << " " << ans << endl;

    if (a == b) return ans;

    for (int i = 19; i >= 0; i--) {
      if (lift[a][i] != lift[b][i]) {
        ans = join(ans, path[a][i]);
        ans = join(ans, path[b][i]);
        a = lift[a][i];
        b = lift[b][i];
      }
    }
    ans = join(ans, path[a][0]);
    cerr << a << " " << b << " " << ans << endl;
    ans = join(ans, path[b][0]);
    cerr << a << " " << b << " " << ans << endl;
    return ans;
  }
};

int N, M;
SegTree stT, stH;
v<int> t, h;
v<int> sig;
DSU dsu;
Tree tmn, tmx;

void initialize(std::vector<int> T, std::vector<int> H) {
  t = T;
  h = H;
  N = T.size();
  M = H.size();
  //rep(i, 0, N) {rep(j, 0, M) {if (T[i] > H[j]) cout << 1 << " ";else cout << 0 << " ";}cout << endl;}
  stT = SegTree(N);
  stH = SegTree(M);
  rep(i, 0, N) {
    stT.build(1, 0, N-1, i, T[i]);
  }
  rep(i, 0, M) {
    stH.build(1, 0, M-1, i, H[i]);
  }
  dsu = DSU(M);
  tmn.init(M, 0);
  tmx.init(M, 1);
  v<int> ord(M);
  rep(i, 0, M) ord[i] = i;
  sort(ord.begin(), ord.end(), [&](int x, int y) {
    return H[x] < H[y];
  });
  v<int> mnr(M, N);
  int pointer = 0;
  rep(i, 0, N) {
    while (pointer < M && H[ord[pointer]] < T[i]) {
      mnr[ord[pointer]] = i;
      pointer++;
    }
  }
  v<bool> used(M, false);
  for (auto i : ord) {
    if (i > 0 && used[i-1]) {
      int x = dsu.find(i-1);

      int L = dsu.L[x];
      int R = dsu.R[x];

      int a = mnr[x];
      int b = mnr[i];

      int val = stT.query(1, 0, N-1, a, b);
      if (b == N) val = 0;

      int vmn = stH.find_first(1, 0, M-1, L, val);
      if (vmn > R) vmn = 1e9;
      int vmx = stH.find_last(1, 0, M-1, R, val);
      if (vmx < L) vmx = -1e9;
      tmx.add(x, i, vmn);
      tmn.add(x, i, vmx);

      dsu.unite(i, i-1);
    }

    if (i < M-1 && used[i+1]) {
      int x = dsu.find(i+1);

      int L = dsu.L[x];
      int R = dsu.R[x];

      int a = mnr[x];
      int b = mnr[i];

      int val = stT.query(1, 0, N-1, a, b);
      if (b == N) val = 0;

      int vmn = stH.find_first(1, 0, M-1, L, val);
      if (vmn > R) vmn = 1e9;
      int vmx = stH.find_last(1, 0, M-1, R, val);
      if (vmx < L) vmx = -1e9;
      tmx.add(x, i, vmn);
      tmn.add(x, i, vmx);

      dsu.unite(i, i+1);
    }
    used[i] = true;
  }

  tmn.prepare(ord.back());
  tmx.prepare(ord.back());
  return;
}

bool can_reach(int L, int R, int s, int d) {
  if (tmx.weight(s, d) <= R && tmn.weight(s, d) >= L) return true;
  else return false;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17