結果

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

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
//#include "atcoder/all"

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")

using namespace std;

using i64 = long long;


template<typename T> class CHT {
private:
  struct node {
    node *left, *right;
    static const T inf = numeric_limits<T>::max();
    T a, b, l, r;
    node(const T _a, const T _b, const T _l, const T _r)
      : left(nullptr), right(nullptr), a(_a), b(_b), l(_l), r(_r){}
    T f(const T x) const {
      return (l <= x && x < r) ? (a * x + b) : inf;
    }
    T tf(const T x) const {
      return a * x + b;
    }
    bool isLine(const T _l, const T _r) const {
      return (l == _l) && (r == _r);
    }
  };
  static void swap(node *x, node *y){
    std::swap(x->a, y->a), std::swap(x->b, y->b), std::swap(x->l, y->l), std::swap(x->r, y->r);
  }
  void _add_segment(node *cur, node *nw, T l, T r){
    while(true){
      const T mid = (l + r) / 2;
      if(cur->f(nw->l) <= nw->tf(nw->l) && cur->f(nw->r - 1) <= nw->tf(nw->r - 1)){
        break;
      }
      if(cur->tf(cur->l) >= nw->f(cur->l) && cur->tf(cur->r - 1) >= nw->f(cur->r - 1)){
        swap(cur, nw);
        break;
      }
      if(cur->isLine(l, r) && nw->isLine(l, r)){
        if(nw->tf(l) < cur->tf(l)) swap(cur, nw);
        if(cur->tf(mid) <= nw->tf(mid)){
          if(!cur->right){
            cur->right = new node(nw->a, nw->b, mid, r);
            break;
          }else{
            cur = cur->right, l = mid, nw->l = mid;
          }
        }else{
          swap(cur, nw);
          if(!cur->left){
            cur->left = new node(nw->a, nw->b, l, mid);
            break;
          }else{
            cur = cur->left, r = mid, nw->r = mid;
          }
        }
        continue;
      }
      if(nw->isLine(l, r)) swap(cur, nw);
      if(nw->r <= mid){
        if(!cur->left){
          cur->left = new node(*nw);
          break;
        }else{
          cur = cur->left, r = mid;
        }
      }else if(mid <= nw->l){
        if(!cur->right){
          cur->right = new node(*nw);
          break;
        }else{
          cur = cur->right, l = mid;
        }
      }else{
        node _nw(nw->a, nw->b, mid, nw->r);
        nw->r = mid;
        if(!cur->left){
          cur->left = new node(*nw);
        }else{
          _add_segment(cur->left, nw, l, mid);
        }
        if(!cur->right){
          cur->right = new node(_nw);
        }else{
          _add_segment(cur->right, &_nw, mid, r);
        }
        break;
      }
    }
  }
  T query(node *cur, const T k, T l, T r) const {
    T ans = numeric_limits<T>::max();
    while(cur){
      ans = min(ans, cur->f(k));
      const T mid = (l + r) / 2;
      if(k < mid){
        cur = cur->left, r = mid;
      }else{
        cur = cur->right, l = mid;
      }
    }
    return ans;
  }
  void clear(node *cur){
    if(cur->left) clear(cur->left);
    if(cur->right) clear(cur->right);
    delete cur;
  }
  const T lpos, rpos;
  node *root;
public:
  CHT(const T _lpos, const T _rpos)
    : lpos(_lpos), rpos(_rpos),
      root(new node(0, numeric_limits<T>::max(), lpos, rpos)){
    assert(lpos < rpos);
  }
  // ~CHT(){ clear(root); }
  // f(x) = a * x + b を挿入
  void add_line(const T a, const T b){
    node nw(a, b, lpos, rpos);
    return _add_line(root, &nw, lpos, rpos);
  }
  // f(x) = a * x + b (x ∈ [l, r)) を挿入
  void add_segment(const T a, const T b, const T l, const T r){
    assert(l < r);
    node nw(a, b, l, r);
    return _add_segment(root, &nw, lpos, rpos);
  }
  // x = k での最小値
  T query(const T k) const {
    return query(root, k, lpos, rpos);
  }
};

void solve(){
  int n, q;
  cin >> n >> q;

  CHT<i64> cht(0, n + 1);
  cht.add_segment(1, -1, 1, n + 1);

  for(int i = 0; i < q; ++i){
    int ty;
    cin >> ty;
    if(ty == 1){
      int x;
      cin >> x;
      cout << cht.query(x) << endl;
    }
    else{
      int x;
      i64 c;
      cin >> x >> c;
      cht.add_segment(1, c - x, x, n + 1);
      cht.add_segment(-1, c + x, 0, x);
    }
  }
}

signed main(){
  solve();
}
0