結果

問題 No.2404 Vertical Throw Up
コンテスト
ユーザー Taiki0715
提出日時 2023-08-04 22:03:39
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 114 ms / 2,000 ms
コード長 3,685 bytes
コンパイル時間 1,743 ms
コンパイル使用メモリ 129,752 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-14 20:00:23
合計ジャッジ時間 3,173 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <iostream>
#include <limits>
#include <map>
#include <vector>

template <typename L, typename R>
class bimap {
  std::map<L, R> M_ltor;
  std::map<R, L> M_rtol;

public:
  bimap() = default;

  void insert(L l, R r) {
    if (auto it = M_ltor.lower_bound(l); it != M_ltor.end() && it->first == l) {
      R old_r = it->second;
      M_rtol.erase(old_r);
      it->second = r;
    } else {
      M_ltor.emplace_hint(it, l, r);
    }
    if (auto it = M_rtol.lower_bound(r); it != M_rtol.end() && it->first == r) {
      L old_l = it->second;
      M_ltor.erase(old_l);
      it->second = l;
    } else {
      M_rtol.emplace_hint(it, r, l);
    }
  }

  void erase_left(L l) {
    if (auto it = M_ltor.find(l); it != M_ltor.end()) {
      auto r = it->second;
      M_rtol.erase(r);
      M_ltor.erase(it);
    }
  }

  L right_ge(R r) {
    auto it = M_rtol.lower_bound(r);
    assert(it != M_rtol.end());
    return it->second;
  }
};

template <typename I>
class cht {
  std::map<I, I> M_f;
  bimap<I, I> M_range;
  
public:
  cht() = default;

  void push(I a, I b) {
    if (M_f.empty()) {
      auto max = std::numeric_limits<I>::max();
      M_f.insert({a, b});
      M_range.insert(a, max);
      return;
    }
    if (M_unused(a, b)) {
      return;
    }
    M_remove_unused(a, b);
    M_insert(a, b);
  }

  I min(I x) {
    I a = M_range.right_ge(x);
    I b = M_f[a];
    return a * x + b;
  }

private:
  bool M_unused(I a, I b) {
    auto itl = M_f.lower_bound(a);
    if (itl == M_f.end()) return false;
    auto [al, bl] = *itl;
    if (a == al) return bl <= b;
    if (itl == M_f.begin()) return false;
    auto itr = std::prev(itl);
    auto [ar, br] = *itr;
    return S_right(al, bl, a, b) >= S_right(a, b, ar, br);
  }

  void M_remove_unused(I a, I b) {
    M_f.erase(a);
    M_range.erase_left(a);

    std::vector<I> rm;
    do {
      auto itl = M_f.lower_bound(a);
      if (itl == M_f.end()) break;
      auto itll = std::next(itl);
      while (itll != M_f.end()) {
        auto [all, bll] = *itll;
        auto [al, bl] = *itl;
        if (S_right(all, bll, al, bl) >= S_right(al, bl, a, b)) {
          rm.push_back(al);
        } else {
          break;
        }
        itl = itll++;
      }
    } while (false);
    do {
      auto itr = M_f.lower_bound(a);
      if (itr == M_f.begin()) break;
      auto itrr = std::prev(itr);
      while (itrr != M_f.begin()) {
        itr = itrr--;
        auto [arr, brr] = *itrr;
        auto [ar, br] = *itr;
        if (S_right(a, b, ar, br) >= S_right(ar, br, arr, brr)) {
          rm.push_back(ar);
        } else {
          break;
        }
      }
    } while (false);
    for (auto ar: rm) {
      M_f.erase(ar);
      M_range.erase_left(ar);
    }
  }

  void M_insert(I a, I b) {
    auto it = M_f.lower_bound(a);
    if (it != M_f.end()) {
      auto [al, bl] = *it;
      M_range.insert(al, S_right(al, bl, a, b));
    }
    if (it != M_f.begin()) {
      auto [ar, br] = *std::prev(it);
      M_range.insert(a, S_right(a, b, ar, br));
    } else {
      M_range.insert(a, std::numeric_limits<I>::max());
    }
    M_f.insert({a, b});
  }

  static I S_right(I a, I b, I ar, I br) {
    return S_div_euclid(br - b, a - ar);
  }

  static I S_div_euclid(I num, I den) {
    if (num % den == 0 || num >= 0) return num / den;
    return num / den + 1;
  }
};

using namespace std;
using ll=long long;
int main() {
  ll a;
  int q;
  cin>>a>>q;
  cht<ll>cht;
  while(q--){
    int op;
    cin>>op;
    if(op==1){
      ll s,t;
      cin>>s>>t;
      cht.push(-(s+t),s*t);
    }
    else{
      ll s;
      cin>>s;
      cout<<max(0ll,-cht.min(s)*a-a*s*s)<<endl;
    }
  }
}
0