제출 #1326156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326156		Numberz	장애물 (IOI25_obstacles)	C++20	58 / 100	147 ms	42880 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int MAXM = 2e5+5;
struct UF {
  vector<int> key, sz;
  UF(int n) {
    for (int i = 0; i <= n; i++) {
      key.push_back(i);
      sz.push_back(1);
    }
  }
  
  int find(int x) {return key[x] == x ? x : key[x] = find(key[x]);}

  void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a==b) return;
    if (sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    key[b] = a;
  }
};
UF comps(MAXM);
vector<bool> bad(MAXM, 0);

void initialize(vector<int> T, vector<int> H) {
  
  int n = T.size(), m = H.size();

  //row with highest temp of the top i
  vector<int> premn(n, 0);
  premn[0] = T[0];
  for (int i = 1; i < n; i++) premn[i] = min(T[i], premn[i-1]);

  //highest temp row we can reach from col i by going straight down
  vector<int> optrow(m);
  for (int i = 0; i < m; i++) {
    if (T[0] <= H[i]) {
      optrow[i] = -1;
      bad[i] = 1;
    }
    else {
      int l = 0, r = n-1;
      while (l < r) {
        int md = (l + r + 1) / 2;
        if (premn[md] <= H[i]) r = md-1;
        else l = md;
      }
      optrow[i] = l;
    }
  }


  //sparse table for rmq of H[i]
  vector<vector<int>> mnst(20, vector<int>(m)), mxst(20, vector<int>(m));
  for (int i = 0; i < m; i++) mnst[0][i] = mxst[0][i] = i;
  for (int b = 1; b < 20; b++) for (int i = 0; i < m; i++) {
    int j = i + (1<<(b-1));
    if (j >= m) {
      mnst[b][i] = mnst[b-1][i];
      mxst[b][i] = mxst[b-1][i];
    }
    else {
      mnst[b][i] = (H[mnst[b-1][i]] < H[mnst[b-1][j]] ? mnst[b-1][i] : mnst[b-1][j]);
      mxst[b][i] = (H[mxst[b-1][i]] > H[mxst[b-1][j]] ? mxst[b-1][i] : mxst[b-1][j]);
    }
  }
  auto qry = [&](int l, int r, bool mn) -> int {
    int b = 20;
    while ((1<<b) > r - l + 1) b--;
    if (mn) return (H[mnst[b][l]] < H[mnst[b][r - (1<<b) + 1]] ? mnst[b][l] : mnst[b][r - (1<<b) + 1]);
    else return (H[mxst[b][l]] > H[mxst[b][r - (1<<b) + 1]] ? mxst[b][l] : mxst[b][r - (1<<b) + 1]);
  };

  //now we need to somehow unite everything in our dsu
  //we maintain for each col, what the furthest left and right we can go in that interval is
  vector<int> mostleft(m, -1), mostright(m, -1);
  for (int i = 0; i < m; i++) {
    if (optrow[i] == -1) continue;
    int t = T[optrow[i]];
    int l = 0, r = i;
    while (l < r) {
      int md = (l + r) / 2;
      if (H[qry(md, i, 0)] >= t) l = md+1;
      else r = md;
    }
    mostleft[i] = l;
    l = i, r = m-1;
    while (l < r) {
      int md = (l + r + 1) / 2;
      if (H[qry(i, md, 0)] >= t) r = md-1;
      else l = md;
    }
    mostright[i] = l;

  }

  //now imagine the process as jumping up segemnts, each being associated with its deepest col, so we have a tree on cols
  //the parent of a col is the best col within its segment, then we simply do UF
  for (int i = 0; i < m; i++) {
    if (optrow[i] == -1) continue;
    int p = qry(mostleft[i], mostright[i], 1);
    comps.unite(i, p);
  }

}

bool can_reach(int L, int R, int S, int D) {
  if (bad[S] || bad[D]) return false;
  return comps.find(S) == comps.find(D);
}

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