結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー k1suxu
提出日時 2025-04-19 22:45:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,843 bytes
コンパイル時間 3,225 ms
コンパイル使用メモリ 276,772 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-19 22:45:47
合計ジャッジ時間 6,201 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using std::cin;
using std::cout;

#define rep(i,n) for(int i = 0; i < (int)n; i++)
#define FOR(n) for(int i = 0; i < (int)n; i++)
#define repi(i,a,b) for(int i = (int)a; i < (int)b; i++)
#define all(x) x.begin(),x.end()
//#define mp make_pair
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvvvi vector<vvvi>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>

template<typename T>
bool chmax(T &a, const T b) {if(a<b) {a=b; return true;} else {return false;}}
template<typename T>
bool chmin(T &a, const T b) {if(a>b) {a=b; return true;} else {return false;}}

using ll = long long;
using ld = long double;
using ull = unsigned long long;

const ll INF = numeric_limits<long long>::max() / 2;
const ld pi = 3.1415926535897932384626433832795028;
const ll mod = 998244353;
int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};

#define int long long

// ref: https://kopricky.github.io/code/DataStructure_Advanced/dynamic_convex_hull_trick.html
template<typename T, bool isMin>
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_line(node *cur, node *nw, T l, T r){
        while(true){
            if(nw->f(l) < cur->f(l)) swap(cur, nw);
            if(cur->f(r - 1) <= nw->f(r - 1)) break;
            const T mid = (l + r) / 2;
            if(cur->f(mid) <= nw->f(mid)){
                if(!cur->right){
                    cur->right = new node(*nw);
                    break;
                }else{
                    cur = cur->right, l = mid;
                }
            }else{
                swap(cur, nw);
                if(!cur->left){
                    cur->left = new node(*nw);
                    break;
                }else{
                    cur = cur->left, r = mid;
                }
            }
        }
    }
    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(T a, T b){
        if(!isMin) a = -a, b = -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 l, const T r, T a, T b){
        if(!isMin) a = -a, b = -b;
        assert(l < r);
        node nw(a, b, l, r);
        return _add_segment(root, &nw, lpos, rpos);
    }
    // x = k での最小値
    T query(const T k) const {
        if(!isMin) return -query(root, k, lpos, rpos);
        return query(root, k, lpos, rpos);
    }
};

/*注意*/
/*isMin = false すなわちmaxをとるクエリはverifyした*/  // verify ref: https://atcoder.jp/contests/abc353/submissions/53476459
// query(x) == numeric_limits<long long>::max() -> そこに線分は存在しない

void solve() {
    int n, q;
    cin >> n >> q;
    CHT<int, true> cht(0, n);
    cht.add_line(1, 0);
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            x--;
            cout << cht.query(x) << endl;
        } else {
            int x, c;
            cin >> x >> c;
            x--;
            cht.add_segment(x, n, 1, c-x);
        }
    }
}

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