#898994 (C++14) No.2404 Vertical Throw Up

提出ソース

結果

問題	No.2404 Vertical Throw Up
ユーザー	蜜蜂
提出日時	2023-08-05 10:53:18
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	80 ms / 2,000 ms
コード長	4,466 bytes
コンパイル時間	4,242 ms
コンパイル使用メモリ	237,248 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-04-23 08:13:15
合計ジャッジ時間	6,069 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	63 ms 6,944 KB
testcase_04	AC	53 ms 6,944 KB
testcase_05	AC	79 ms 6,944 KB
testcase_06	AC	3 ms 6,940 KB
testcase_07	AC	80 ms 6,940 KB
testcase_08	AC	63 ms 6,944 KB
testcase_09	AC	51 ms 6,940 KB
testcase_10	AC	16 ms 6,940 KB
testcase_11	AC	15 ms 6,944 KB
testcase_12	AC	10 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	3 ms 6,940 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	3 ms 6,944 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	3 ms 6,944 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	3 ms 6,940 KB
testcase_24	AC	3 ms 6,940 KB
testcase_25	AC	3 ms 6,940 KB
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	2 ms 6,940 KB
testcase_29	AC	2 ms 6,944 KB
testcase_30	AC	3 ms 6,944 KB
testcase_31	AC	3 ms 6,940 KB
testcase_32	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

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] = *

ソースコード

raw source code

// 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;
    }
  }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード