結果
問題 | No.2404 Vertical Throw Up |
ユーザー | Taiki0715 |
提出日時 | 2023-08-04 22:03:39 |
言語 | C++17(clang) (17.0.6 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 88 ms
5,248 KB |
testcase_04 | AC | 70 ms
5,248 KB |
testcase_05 | AC | 109 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 114 ms
5,248 KB |
testcase_08 | AC | 86 ms
5,248 KB |
testcase_09 | AC | 68 ms
5,248 KB |
testcase_10 | AC | 19 ms
5,248 KB |
testcase_11 | AC | 19 ms
5,248 KB |
testcase_12 | AC | 14 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 3 ms
5,248 KB |
testcase_15 | AC | 3 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 3 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 3 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | AC | 3 ms
5,248 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 3 ms
5,248 KB |
testcase_27 | AC | 2 ms
5,248 KB |
testcase_28 | AC | 2 ms
5,248 KB |
testcase_29 | AC | 2 ms
5,248 KB |
testcase_30 | AC | 2 ms
5,248 KB |
testcase_31 | AC | 2 ms
5,248 KB |
testcase_32 | AC | 2 ms
5,248 KB |
ソースコード
#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; } } }