結果

問題 No.2404 Vertical Throw Up
コンテスト
ユーザー silv723
提出日時 2023-08-04 21:52:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 180 ms / 2,000 ms
コード長 6,363 bytes
コンパイル時間 4,863 ms
コンパイル使用メモリ 286,972 KB
最終ジャッジ日時 2025-02-15 22:38:46
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace atcoder;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll=long long;
using ld=long double;
using ull=unsigned long long;
using i128 = __int128_t;
#define vs vector<string>
#define rep(i,n) for(ll i=0;i<ll(n);i++)
#define rep2(i,n) for(ll i=n-1;i>=0;i--)
#define rep3(i,a,b) for(ll i=a;i<=ll(b);i++)
#define rep4(i,a,b) for(ll i=a;i>=ll(b);i--)
#define forv(i,V) for(const auto& i:V)
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define SIZE(x) int(x.size())
constexpr ll mod=998244353;
//constexpr ll mod=1000000007;
#define pi 3.14159265358979323
#define INF32 2147483647
#define INF64 9223372036854775807
#define faster ios::sync_with_stdio(false);std::cin.tie(nullptr)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define rev reverse
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>
#define prq priority_queue
#define lb lower_bound
#define ub upper_bound
#define popcnt __builtin_popcountll
#define TLE while(true);
#define RE assert(false);
#define MLE vector<vector<vector<long long>>> mle_mle(400,vector<vector<long long>>(1000,vector<long long>(1000)));
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
#define rall(n) (n).rbegin(),(n).rend()
#define INT(...) int __VA_ARGS__;scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__)
template<typename T,typename U>
ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T,typename U>
istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<typename T>
ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>
istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}
void scan(){}
template<class Head,class... Tail>
void scan(Head&head,Tail&... tail){cin>>head;scan(tail...);}
template<class T>
void print(const T &t){cout<<t<<'\n';}
template<class Head, class... Tail>
void print(const Head &head, const Tail &... tail){cout<<head<<' ';print(tail...);}
template<class... T>
void fin(const T &... a){print(a...);exit(0);}
ll max(int a,ll b){return max((ll)a,b);}
ll max(ll a,int b){return max((ll)b,a);}
ll min(int a,ll b){return min((ll)a,b);}
ll min(ll a,int b){return min((ll)b,a);}
//a以上b以下の個数
template<typename T>
ll RangeOK(ll a,ll b,vector<T> &v){
  return max(ub(all(v),b)-lb(all(v),a),0);
}
template <typename T>
vector<T> compress(vector<T> &X) {
    vector<T> vals = X;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 0; i < (int)X.size(); i++) {
        X[i] = lower_bound(vals.begin(), vals.end(), X[i]) - vals.begin();
    }
    return vals;
}
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
template<typename T, typename U, size_t sz = (1LL<<20), U eps = 1>
struct LiChaoTree{
  template <class P, class Q>
  inline bool chmax(P &a, const Q &b) {
    return (a < b ? a = b, 1 : 0);
  }
  template <class P, class Q>
  inline bool chmin(P &a, const Q &b) {
    return (a > b ? a = b, 1 : 0);
  }
  struct Line{
    T a, b, c;
    constexpr Line(T a, T b, T c):a(a), b(b), c(c){};
    constexpr Line():Line(0, 0, numeric_limits<T>::max()){};
    T operator()(U x) const {return a*x*x+b*x+c;};
  };
  struct Node{
    Line f;
    Node *l, *r;
  };
  int index;
  Node *NODE, *root;
  U L, R;
  LiChaoTree(U L, U R):index(0),root(nullptr),L(L),R(R){
    NODE = new Node[sz];
  };
  Node *new_node(){
  	NODE[index].f = Line();
    return &(NODE[index++]);
  }
  void insert_segment(U xl, U xr, T a, T b, T c){
  	assert(L <= xl && xl < xr && xr <= R);
    Line f(a, b, c);
    if(!root) root = new_node();
    insert_segment_sub(root, xl, xr, f, L, R);
  }
  void insert_line(T a, T b, T c){insert_segment(L, R, a, b, c);}
  T get_min(U x){
  	assert(L <= x && x < R);
    if(!root) return numeric_limits<T>::max();
    return min_sub(root, x, L, R);
  }
private:
  void insert_segment_sub(Node *rt, U xl, U xr, const Line &f, U l, U r){
  	chmax(xl, l);
    chmin(xr, r);
    if(xl >= xr) return;
    if(l < xl || xr < r){
      U mid = (l+r)/2;
      if(!rt->l) rt->l = new_node();
      if(!rt->r) rt->r = new_node();
      insert_segment_sub(rt->l, xl, xr, f, l, mid);
      insert_segment_sub(rt->r, xl, xr, f, mid, r);
    }else{
      insert_line_sub(rt, f, l, r);
    }
  }
  void insert_line_sub(Node *rt, const Line &f, U l, U r){
    T fl = f(l), fr = f(r-eps);
    Line g = rt->f;
    T gl = g(l), gr = g(r-eps);
    if(fl >= gl && fr >= gr) return;
    if(fl <= gl && fr <= gr){
      rt->f = f;
      return;
    }
    U mid = (l+r)/2;
    T fm = f(mid), gm = g(mid);
    if(fm <= gm){
      rt->f = f;
      if(fl < gl){
        if(!rt->r) rt->r = new_node();
        insert_line_sub(rt->r, g, mid, r);
      }else{
        if(!rt->l) rt->l = new_node();
        insert_line_sub(rt->l, g, l, mid);
      }
    }else{
      if(gl < fl){
        if(!rt->r) rt->r = new_node();
        insert_line_sub(rt->r, f, mid, r);
      }else{
        if(!rt->l) rt->l = new_node();
        insert_line_sub(rt->l, f, l, mid);
      }
    }
  }
  T min_sub(Node *rt, U x, U l, U r){
    T ret = rt->f(x);
    U mid = (l+r)/2;
    if(x < mid && rt->l) return min(ret, min_sub(rt->l, x, l, mid));
    if(x >= mid && rt->r) return min(ret, min_sub(rt->r, x, mid, r));
    return ret;
  }
};
int main(){
  LL(a);
  INT(q);
  LiChaoTree<__int128_t, __int128_t> lct(-(1LL<<60), (1LL<<60));
  rep(i, q){
    INT(z);
    if(z == 1){
      LL(s, t);
      lct.insert_line(a, -a*(s+t), a*s*t);
    }else{
      LL(x);
      auto y = lct.get_min(x);
      y = min(y, (__int128_t)0);
      print(-(ll)y);
    }
  }
}
0