結果

問題 No.3116 More and more teleporter
ユーザー GOTKAKO
提出日時 2025-04-18 21:22:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 50 ms / 2,000 ms
コード長 4,518 bytes
コンパイル時間 2,016 ms
コンパイル使用メモリ 195,004 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-04-18 21:22:18
合計ジャッジ時間 3,736 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
In constructor ‘ConvexHullTrick2<T>::ConvexHullTrick2() [with T = int]’,
    inlined from ‘int main()’ at main.cpp:110:27:
main.cpp:91:65: warning: ‘*(__vector(2) int*)((char*)&Z + offsetof(ConvexHullTrick2<int>,ConvexHullTrick2<int>::Left))’ is used uninitialized [-Wuninitialized]
   91 |     ConvexHullTrick2():Left(-1073741824),Right(1073741824),root(new Node(0,numeric_limits<T>::max(),Left,Right)){}
      |                                                                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:110:27: note: ‘Z’ declared here
  110 |     ConvexHullTrick2<int> Z;
      |                           ^

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template<typename T>
class ConvexHullTrick2{ //区間バージョン.
    private:
    struct Node{
        T a,b,l,r;
        Node *LR[2];
        static const T inf = numeric_limits<T>::max();
        Node(T aa,T bb,T ll,T rr):a(aa),b(bb),l(ll),r(rr),LR{nullptr,nullptr}{}
        T f(T x){
            if(l <= x && x < r) return a*x+b;
            return inf;
        }
        T g(T x){return a*x+b;}
        bool isline(T ll,T rr){return (l==ll && r==rr);}
    };
    Node *root;
    T Left,Right = 1;
    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 addline(T l,T r,Node *p,Node *now){
        while(true){
            if(now->f(l) < p->f(l)) swap(p,now);
            if(p->f(r-1) <= now->f(r-1)) break;
            T m = (l+r)/2;
            if(p->f(m) <= now->f(m)){
                if(p->LR[1] == nullptr){p->LR[1] = new Node(m,r,now->a,now->b); break;}
                p = p->LR[1]; l = m; now->l = m;
            }
            else{
                swap(p,now);
                if(p->LR[0] == nullptr){p->LR[0] = new Node(l,m,now->a,now->b); break;}
                p = p->LR[0]; r = m; now->r = m;
            }
        }
    }
    void addsegment(T l,T r,Node *p,Node *now){ //勝ち負けはnew目線.
        while(true){
            T m = (l+r)/2;
            if(p->f(now->l) <= now->g(now->l) && p->f(now->r-1) <= now->g(now->r-1)) break; //newの両端どっちも負け->不採用.
            if(p->g(p->l) >= now->f(p->l) && p->g(p->r-1) >= now->f(p->r-1)){swap(p,now); break;} //oldの両端どっちも勝ち->採用.
            if(p->isline(l,r) && now->isline(l,r)){ //どちらも今見ているl,rと範囲同じならaddline.
                if(now->g(l) < p->g(l)) swap(p,now);
                if(p->g(r-1) <= now->g(r-1)) break;
                T m = (l+r)/2;
                if(p->g(m) <= now->g(m)){
                    if(p->LR[1] == nullptr){p->LR[1] = new Node(now->a,now->b,m,r); break;}
                    p = p->LR[1]; l = m; now->l = m;
                }
                else{
                    swap(p,now);
                    if(p->LR[0] == nullptr){p->LR[0] = new Node(now->a,now->b,l,m); break;}
                    p = p->LR[0]; r = m; now->r = m;
                }
                continue;
            }
            if(now->isline(l,r)) swap(p,now); //oldがlr一致にする.
            if(now->r <= m){ //右端がm以下なら[m,r)は無視.
                if(p->LR[0] == nullptr){p->LR[0] = new Node(*now); break;}
                p = p->LR[0],r = m;
            }
            else if(m <= now->l){ //左端がm以上なら[l,m)は無視.
                if(p->LR[1] == nullptr){p->LR[1] = new Node(*now); break;}
                p = p->LR[1],l = m;
            }
            else{ //左右に分割.
                Node now2(now->a,now->b,m,now->r);
                now->r = m;
                if(p->LR[0] == nullptr) p->LR[0] = new Node(*now);
                else addsegment(l,m,p->LR[0],now);
                if(p->LR[1] == nullptr) p->LR[1] = new Node(now2);
                else addsegment(m,r,p->LR[1],&now2);
                break;
            }
        }
    }
    T findans(T l,T r,Node *p,T x){
        T ret = numeric_limits<T>::max();
        while(p != nullptr){
            ret = min(ret,p->f(x));
            if(x < (l+r)/2) p = p->LR[0],r = (l+r)/2;
            else p = p->LR[1],l = (l+r)/2;
        }
        return ret;
    }
    public:
    ConvexHullTrick2():Left(-1073741824),Right(1073741824),root(new Node(0,numeric_limits<T>::max(),Left,Right)){}
    void make(T L,T R){
        Right = 1;
        while(Right < max(L,R)) Right *= 2;
        Left = -Left;
    } 
    void addline(T a,T b){Node now(a,b,Left,Right); addline(Left,Right,root,&now);}
    void addsegment(T l,T r,T a,T b){
        Node now(a,b,l,r);
        addsegment(Left,Right,root,&now);
    } //[l,r)だよ.
    T query(T x){return findans(Left,Right,root,x);}
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,Q; cin >> N >> Q;
    ConvexHullTrick2<int> Z;
    Z.addsegment(0,N,1,0);
    while(Q--){
        int t; cin >> t;
        if(t == 1){
            int x; cin >> x; x--;
            cout << Z.query(x) << "\n";
        }
        if(t == 2){
            int x,c; cin >> x >> c; x--;
            Z.addsegment(x,N,1,c-x);
            Z.addsegment(0,x,-1,c+x);
        }
    }
}
0