#898527 (C++17) No.2404 Vertical Throw Up

提出ソース
結果

問題	No.2404 Vertical Throw Up
コンテスト
ユーザー	tonegawa
提出日時	2023-08-04 22:19:23
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	112 ms / 2,000 ms
コード長	8,394 bytes
コンパイル時間	1,231 ms
コンパイル使用メモリ	136,348 KB
最終ジャッジ日時	2025-02-15 22:54:08
ジャッジサーバーID （参考情報）	judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 30
権限があれば一括ダウンロードができます
ソースコード

raw source code
#line 1 ".lib/template.hpp"


#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz;i++){
    int m = v[i].size();
    for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
  }
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<(int)sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}
void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

#line 2 "b.cpp"

template<typename Val>
struct lichao_tree{
  static constexpr Val inf = std::numeric_limits<Val>::max();
  Val x_low, x_high;
  struct line{
    Val a, b, c;
    line(Val a, Val b, Val c): a(a), b(b), c(c){}
    inline Val get(Val x){return a * x * x + b * x + c;}
    bool operator != (const line &r){return a != r.a || b != r.b;}
  };
private:
  struct node{
    line x;
    node *l, *r;
    node(const line &x) : x(x), l(nullptr), r(nullptr){}
  };
  node *root;
  node *add_line(node *v, line &x, Val l, Val r, Val x_l, Val x_r){
    if(!v) return new node(x);
    Val t_l = v->x.get(l), t_r = v->x.get(r);
    if(l + 1 == r){
      if(x_l < t_l) v->x = x;
      return v;
    }else if(t_l <= x_l && t_r <= x_r){
      return v;
    }else if(t_l >= x_l && t_r >= x_r){
      v->x = x;
      return v;
    }else{
      Val m = (l + r) / 2;
      Val t_m = v->x.get(m), x_m = x.get(m);
      if(t_m > x_m){
        std::swap(v->x, x);
        if(x_l >= t_l) v->l = add_line(v->l, x, l, m, t_l, t_m);
        else v->r = add_line(v->r, x, m, r, t_m, t_r);
      }else{
        if(t_l >= x_l) v->l = add_line(v->l, x, l, m, x_l, x_m);
        else v->r = add_line(v->r, x, m, r, x_m, x_r);
      }
      return v;
    }
  }
  node *add_segment(node *v, line &x, Val a, Val b, Val l, Val r, Val x_l, Val x_r){
    if(r <= a || b <= l) return v;
    if(a <= l && r <= b){
      line y(x);
      return add_line(v, y, l, r, x_l, x_r);
    }
    if(v){
      Val t_l = v->x.get(l), t_r = v->x.get(r);
      if(t_l <= x_l && t_r <= x_r) return v;
    }else{
      v = new node(line(0, inf));
    }
    Val m = (l + r) / 2;
    Val x_m = x.get(m);
    v->l = add_segment(v->l, x, a, b, l, m, x_l, x_m);
    v->r = add_segment(v->r, x, a, b, m, r, x_m, x_r);
    return v;
  }
  Val min(node *v, Val l, Val r, Val x){
    if(!v) return inf;
    if(l + 1 == r) return v->x.get(x);
    Val m = (l + r) / 2;
    if(x < m) return std::min(v->x.get(x), min(v->l, l, m, x));
    else return std::min(v->x.get(x), min(v->r, m, r, x));
  }
  line min2(node *v, Val l, Val r, Val x){
    if(!v) return line(0, inf);
    if(l + 1 == r) return v->x;
    Val m = (l + r) / 2;
    if(x < m){
      line res = min2(v->l, l, m, x);
      return v->x.get(x) <= res.get(x) ? v->x : res;
    }else{
      line res = min2(v->r, m, r, x);
      return v->x.get(x) <= res.get(x) ? v->x : res;
    }
  }
  // 定数倍高速化できそうだが, addがボトルネックになりがちなのでとりあえずこれで
  void enumerate(node *v, Val l, Val r, std::vector<line> &L, std::vector<std::pair<Val, line>> &res){
    L.push_back(v->x);
    Val m = (l + r) / 2;

    auto calc = [&](Val lx, Val rx)->void{
      while(true){
        line a = min2(lx);
        if(res.empty() || res.back().second != a) res.push_back({lx, a});
        if(a.b == inf) return;
        Val intersection = rx; // min(ceil(交点))
        line next_line = line(0, inf);
        for(int i = 0; i < L.size(); i++){
          if(L[i].b == inf || L[i].a >= a.a) continue;
          // (a.a - L[i].a) x = L[i].b - a.b
          Val diff_a = a.a - L[i].a;
          Val ceil_x = (L[i].b - a.b + diff_a - 1) / diff_a;
          if(lx < ceil_x && ceil_x < intersection){
            assert(lx < ceil_x);
            next_line = L[i];
            intersection = ceil_x;
          }
        }
        if(intersection == rx) break;
        lx = intersection;
      }
    };
    if(v->l && v->r){
      enumerate(v->l, l, m, L, res);
      enumerate(v->r, m, r, L, res);
    }else if(!v->l && !v->r){
      calc(l, r);
    }else if(!v->l){
      calc(l, m);
      enumerate(v->r, m, r, L, res);
    }else{
      enumerate(v->l, l, m, L, res);
      calc(m, r);
    }
    L.pop_back();
  }
public:
  lichao_tree(Val x_low, Val x_high): x_low(x_low), x_high(x_high), root(nullptr){}
  // 直線ax + bを追加
  void add_line(Val a, Val b, Val c){
    line x(a, b, c);
    root = add_line(root, x, x_low, x_high + 1, x.get(x_low), x.get(x_high + 1));
  }
  // 線分ax + b, [l, r)を追加
  void add_segment(Val l, Val r, Val a, Val b, Val c){
    line x(a, b);
    root = add_segment(root, x, l, r, x_low, x_high + 1, x.get(x_low), x.get(x_high + 1));
  }
  // f(x)の最小値
  Val min(Val x){
    return min(root, x_low, x_high + 1, x);
  }
  // f(x)の最小値をとる線
  line min2(Val x){
    return min2(root, x_low, x_high + 1, x);
  }
  // {l, f}, fはl, (次のl)において最小値を取る
  std::vector<std::pair<Val, line>> enumerate(){
    if(!root) return {{x_low, line(0, inf)}};
    std::vector<std::pair<Val, line>> res;
    std::vector<line> L;
    enumerate(root, x_low, x_high + 1, L, res);
    return res;
  }
};

int main(){
  ll a;
  std::cin >> a;
  int q;
  std::cin >> q;
  ll inf_x = 200000000;
  lichao_tree<__int128_t> cht(-inf_x, inf_x);
  range(i, 0, q){
    int _;
    std::cin >> _;
    if(_ == 1){
      ll s, t;
      std::cin >> s >> t;
      cht.add_line(a, -a * (s + t), a * t * s);
    }else{
      ll t;
      std::cin >> t;
      __int128_t ans = cht.min(t);
      if(ans > 0){
        std::cout << 0 << '\n';
      }else{
        std::cout << (ll)-ans << '\n';
      }
    }
  }
}
yukicoder

結果

ソースコード
