結果

問題 No.3116 More and more teleporter
ユーザー タンバリン
提出日時 2025-04-20 13:03:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 149 ms / 2,000 ms
コード長 5,792 bytes
コンパイル時間 1,534 ms
コンパイル使用メモリ 129,848 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-20 13:03:34
合計ジャッジ時間 4,077 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <functional>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include<utility>
#include<stack>
#include <iomanip>
//#include<atcoder/all>
//using namespace atcoder;
using namespace std;
#define P pair<int,int>
#define Graph vector<vector<int>>
#define float long double
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define repi(itr,m) for(auto itr=(m).begin();itr!=(m).end();itr++)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define vi vector<int>
#define int long long
const int INF=1e18;
int dx[8]={0,1,0,-1,-1,-1,1,1};
int dy[8]={1,0,-1,0,-1,1,-1,1};
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false));}
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false));}
struct point{
  int x,y;
};
void yn(bool t){
  if(t)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

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);
    }
};


int solve(){
  int n,q;cin>>n>>q;
  
  CHT<int>g(0,2e5+1);
  g.add_segment(1,-1,0,2e5+1);
  while(q--){
    int t;cin>>t;
    if(t==1){
      int x;cin>>x;
      cout<<g.query(x)<<endl;
    }
    else{
      int x,c;cin>>x>>c;
      g.add_segment(-1,x+c,0,x+1);
      g.add_segment(1,-x+c,x,2e5+1);
    }
  }
  assert(true);
  return 0;
}

signed main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  solve();
}
0