結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー kkk
提出日時 2025-04-20 01:11:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 272 ms / 2,000 ms
コード長 7,027 bytes
コンパイル時間 5,001 ms
コンパイル使用メモリ 260,392 KB
実行使用メモリ 19,672 KB
最終ジャッジ日時 2025-04-20 01:11:12
合計ジャッジ時間 7,970 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace atcoder;
using namespace std;
using ll = long long;
// --------------------------------------------------------
template <class T>
bool chmax(T &a, const T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#define FOR(i, l, r) for (ll i = (l); i < (r); ++i)
#define RFOR(i, l, r) for (ll i = (r) - 1; (l) <= i; --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define MIN(c) *min_element(ALL(c))
#define MAX(c) *max_element(ALL(c))
#define SUM(c) accumulate(ALL(c), 0LL)
#define BITCNT(c) __builtin_popcountll(c)
#define SZ(c) ((int)(c).size())
#define COUT(c) cout << (c) << '\n'
#define debug(x) cerr << #x << " = " << (x) << '\n';
using P = pair<ll, ll>;
using VP = vector<P>;
using VVP = vector<VP>;
using VS = vector<string>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
static const double EPS = 1e-10;
static const double PI = acos(-1.0);
template <typename T>
void arrPrint(vector<T> arr) {
  for (auto v : arr) cout << v << " ";
  cout << '\n';
}
template <typename T>
void arrPrint2Dim(vector<vector<T>> arr) {
  for (auto a : arr) arrPrint(a);
}
template <typename T, typename T2>
void arrPrintPair(vector<pair<T, T2>> arr) {
  for (auto v : arr) cout << "{" << v.first << "," << v.second << "}, ";
  cout << '\n';
}
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

// static const int INF = (1 << 30) - 1;  // 1073741824 - 1
static const ll INF = (1LL << 62) - 1;  // 4611686018427387904 - 1
// static const ll MOD = 1000000007;
static const ll MOD = 998244353;
ll llceil(ll a, ll b) { return (a + b - 1) / b; }
using T = tuple<ll, ll, ll>;

ll Ptoten(VLL &a, ll p) {
  ll res = 0;
  REP(i, SZ(a)) { res = res * p + a[i]; }
  return res;
}

VLL tentoP(ll a, ll p) {
  VLL res;
  if (a == 0) return VLL{0};
  if (p < 2) return res;
  while (a != 0) {
    ll surp = a % p;
    res.push_back(surp);
    a /= p;
  }
  reverse(ALL(res));
  return res;
}

struct mint {
 private:
  long long x;

 public:
  mint(long long x = 0) : x((MOD + x) % MOD) {}
  mint(std::string &s) {
    long long z = 0;
    for (int i = 0; i < SZ(s); i++) {
      z *= 10;
      z += s[i] - '0';
      z %= MOD;
    }
    this->x = z;
  }
  mint &operator+=(const mint &a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint &operator-=(const mint &a) {
    if ((x += MOD - a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint operator-() const {
    mint res(*this);
    return res * -1;
  }
  mint &operator*=(const mint &a) {
    (x *= a.x) %= MOD;
    return *this;
  }
  mint &operator/=(const mint &a) {
    long long n = MOD - 2;
    mint u = 1, b = a;
    while (n > 0) {
      if (n & 1) {
        u *= b;
      }
      b *= b;
      n >>= 1;
    }
    return *this *= u;
  }
  mint operator+(const mint &a) const {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint &a) const {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint &a) const {
    mint res(*this);
    return res *= a;
  }
  mint operator/(const mint &a) const {
    mint res(*this);
    return res /= a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }
  friend std::ostream &operator<<(std::ostream &os, const mint &n) {
    return os << n.x;
  }
  bool operator==(const mint &a) const { return this->x == a.x; }
  bool operator<(const mint &r) { return this->x < r.x; }
  bool operator<=(const mint &r) { return this->x <= r.x; }
  bool operator!=(const mint &r) { return this->x != r.x; }
};
using VM = vector<mint>;
using VVM = vector<vector<mint>>;

// range min, and index (range Mindex)
struct SegmentTree {
  vector<P> A;
  ll N;  // node num

  // 初期化
  SegmentTree(ll size) {
    N = _powerOfTwo(size);  // 2べき
    P initial_value = {(1LL << 31) - 1LL, -1};
    A.resize(N * 2, initial_value);  // 木なので2倍必要
  }

  void update(ll i, ll x) {
    int index = N + i - 1;  // 葉のインデックス
    A[index].first = x;
    A[index].second = i;
    // 親にも反映
    while (index > 0) {
      P min0 = A[index];
      P min1;
      if (index % 2 == 0) {
        min1 = A[index - 1];
      } else {
        min1 = A[index + 1];
      }

      ll parent = (index - 1) / 2;
      A[parent] = min(min0, min1);
      index = parent;
    }
  }

  bool is_power_of_two(ll v) { return !(v & (v - 1)); }

  // 引数以上の2のべき乗 5=>8
  ll _powerOfTwo(int n) {
    ll ret = 1;
    while (ret < n) {
      ret *= 2;
    }
    return ret;
  }

  // 区間[a,b)の総和。ノードk = [l,r) に着目している
  P _rangeMin(int a, int b, int k, int l, int r) {
    // 重ならない
    if (r <= a || b <= l) {
      return {INF, -1};
    }
    // 内包する
    else if (a <= l && r <= b) {
      return A[k];
    }
    // 重なる部分もある
    else {
      ll center = (l + r) / 2;
      // 左下の子
      auto min0 = _rangeMin(a, b, 2 * k + 1, l, center);
      // 右下の子
      auto min1 = _rangeMin(a, b, 2 * k + 2, center, r);
      return min(min0, min1);
    }
  }

  // [a, b) までのmin
  // 半開区間
  P RangeMin(int a, int b) { return _rangeMin(a, b, 0, 0, N); }
};

void solve() {
  ll N, Q;
  cin >> N >> Q;
  // 右でindex+costが最小になるindexをとる
  // 左で-index+costが最小になるindexをとる

  auto segLeft = SegmentTree(N);
  auto segRight = SegmentTree(N);
  REP(i, N) {
    segLeft.update(i, INF);
    segRight.update(i, INF);
  }

  REP(i, Q) {
    ll a, idx, c;
    cin >> a >> idx;
    idx--;
    if (a == 1) {
      ll ans = idx;
      // aより右に飛んでからaに行く
      auto [rightVal, rightIdx] = segRight.RangeMin(idx, N);
      if (rightVal != INF) {
        ll cost = rightVal - rightIdx;
        cost += rightIdx - idx;
        chmin(ans, cost);
      }

      // aより左に飛んでからaに行く
      auto [leftVal, leftIdx] = segLeft.RangeMin(0, idx + 1);
      if (leftVal != INF) {
        ll cost = leftVal + leftIdx;
        cost += idx - leftIdx;
        chmin(ans, cost);
      }
      cout << ans << '\n';

    } else {
      cin >> c;
      ll left = segLeft.RangeMin(idx, idx + 1).first;
      chmin(left, -idx + c);
      segLeft.update(idx, left);
      ll right = segRight.RangeMin(idx, idx + 1).first;
      chmin(right, idx + c);
      segRight.update(idx, right);
    }
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  solve();
}
0