結果

問題 No.2404 Vertical Throw Up
コンテスト
ユーザー 蜜蜂
提出日時 2023-08-05 10:53:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 73 ms / 2,000 ms
コード長 4,466 bytes
コンパイル時間 4,088 ms
コンパイル使用メモリ 241,948 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-15 08:03:06
合計ジャッジ時間 5,597 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'void bimap<L, R>::insert(L, R)':
main.cpp:41:9: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   41 |     if (auto it = M_ltor.lower_bound(l); it != M_ltor.end() && it->first == l) {
      |         ^~~~
main.cpp:48:9: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   48 |     if (auto it = M_rtol.lower_bound(r); it != M_rtol.end() && it->first == r) {
      |         ^~~~
main.cpp: In member function 'void bimap<L, R>::erase_left(L)':
main.cpp:58:9: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   58 |     if (auto it = M_ltor.find(l); it != M_ltor.end()) {
      |         ^~~~
main.cpp: In member function 'bool cht<I>::M_unused(I, I)':
main.cpp:104:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  104 |     auto [al, bl] = *itl;
      |          ^
main.cpp:108:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  108 |     auto [ar, br] = *itr;
      |          ^
main.cpp: In member function 'void cht<I>::M_remove_unused(I, I)':
main.cpp:122:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  122 |         auto [all, bll] = *itll;
      |              ^
main.cpp:123:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  123 |         auto [al, bl] = *itl;
      |              ^
main.cpp:138:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  138 |         auto [arr, brr] = *itrr;
      |              ^
main.cpp:139:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  139 |         auto [ar, br] = *

ソースコード

diff # 

// g++ 1.cpp -std=c++17 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;

using ll = long long;
using ld = long double;
 
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;
 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

// https://judge.yosupo.jp/submission/87787
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;
  }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll a;cin>>a;
  int q;cin>>q;

  cht<ll> ch;

  while(q--){
    int type;cin>>type;

    if(type==1){
      ll s,t;cin>>s>>t;
      ll b=a*(s+t);
      ll c=-a*s*t;
      ch.push(-b,-c);
    }
    else{
      ll t;cin>>t;
      ll g=ch.min(t);
      cout<<max(0ll,-a*t*t-g)<<endl;
    }
  }
}
0