結果
問題 |
No.3116 More and more teleporter
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }