제출 #1257184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257184		flashmt	장애물 (IOI25_obstacles)	C++20	100 / 100	282 ms	87696 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;

vector<vector<pair<int, int>>> jumpLeft, jumpRight;
vector<pair<int, int>> intervals;
int maxLog;

void initialize(vector<int> t, vector<int> h) {
  int n = size(t), m = size(h);
  vector<pair<int, int>> incT = {{t[0], 0}};
  auto decT = incT;
  for (int i = 1; i < n; i++)
  {
    if (t[i] > incT.back().first)
      incT.push_back({t[i], i});
    if (t[i] < decT.back().first)
      decT.push_back({t[i], i});
  }

  vector<vector<pair<int, int>>> eventsAt(n + 1);
  for (int i = 0; i < m; i++)
    if (h[i] < t[0])
    {
      int low = 0, high = size(decT) - 1, res = -1;
      while (low <= high)
      {
        int mid = (low + high) / 2;
        if (h[i] >= decT[mid].first)
        {
          res = mid;
          high = mid - 1;
        }
        else low = mid + 1;
      }

      int row = res < 0 ? n - 1 : decT[res].second - 1;
      eventsAt[row].push_back({1, i});
    }
    else
    {
      int low = 0, high = size(incT) - 1, res = -1;
      while (low <= high)
      {
        int mid = (low + high) / 2;
        if (h[i] < incT[mid].first)
        {
          res = mid;
          high = mid - 1;
        }
        else low = mid + 1;
      }

      int row = res >= 0 ? incT[res].second : n;
      eventsAt[row].push_back({0, i});
    }

  set<pair<int, int>> active = {{-1, 0}, {m, 0}};
  vector<int> l(m), r(m);
  intervals.resize(m);
  for (int row = n; row >= 0; row--)
  {
    sort(rbegin(eventsAt[row]), rend(eventsAt[row]));
    for (auto [isGood, col] : eventsAt[row])
      if (isGood)
      {
        auto it = active.lower_bound({col, 1});
        auto [nextCol, isNextGood] = *it;
        auto [prevCol, isPrevGood] = *prev(it);
        active.insert({col, 1});
        if (isNextGood && isPrevGood)
        {
          l[col] = prevCol;
          r[col] = nextCol;
        }
        else if (isNextGood) l[col] = r[col] = nextCol;
        else if (isPrevGood) l[col] = r[col] = prevCol;
        else l[col] = r[col] = col;
        intervals[col] = {prevCol, nextCol};
      }
      else
      {
        active.insert({col, 0});
        l[col] = r[col] = col;
        intervals[col] = {col, col};
      }
  }

  maxLog = 32 - __builtin_clz(m);
  jumpLeft = jumpRight = vector<vector<pair<int, int>>>(maxLog, vector<pair<int, int>>(m));
  for (int i = 0; i < m; i++)
  {
    jumpLeft[0][i] = {l[i], l[i]};
    jumpRight[0][i] = {r[i], r[i]};
  }

  for (int i = 1; i < maxLog; i++)
    for (int j = 0; j < m; j++)
    {
      auto [jj, bound] = jumpLeft[i - 1][j];
      jumpLeft[i][j] = {jumpLeft[i - 1][jj].first, max(jumpLeft[i - 1][jj].second, bound)};
      tie (jj, bound) = jumpRight[i - 1][j];
      jumpRight[i][j] = {jumpRight[i - 1][jj].first, min(jumpRight[i - 1][jj].second, bound)};
    }
}

bool can_reach(int L, int R, int from, int to) {
  if (from > to)
    swap(from, to);

  if (from + 1 == to)
    return 1;

  int x = from, y = to;
  for (int i = maxLog - 1; i >= 0; i--)
  {
    auto [xx, bound] = jumpRight[i][x];
    if (L <= bound && bound <= R)
      x = xx;
    auto [yy, bound2] = jumpLeft[i][y];
    if (L <= bound2 && bound2 <= R)
      y = yy;
  }
  return intervals[x].second >= to && intervals[y].first <= from;
}

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