結果
問題 | No.2404 Vertical Throw Up |
ユーザー | 👑 emthrm |
提出日時 | 2023-08-04 21:41:17 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 3,889 bytes |
コンパイル時間 | 3,124 ms |
コンパイル使用メモリ | 269,372 KB |
実行使用メモリ | 6,680 KB |
最終ジャッジ日時 | 2024-10-14 19:39:26 |
合計ジャッジ時間 | 4,495 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 22 ms
5,312 KB |
testcase_04 | AC | 18 ms
5,248 KB |
testcase_05 | AC | 28 ms
6,668 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 31 ms
6,680 KB |
testcase_08 | AC | 24 ms
5,320 KB |
testcase_09 | AC | 19 ms
5,248 KB |
testcase_10 | AC | 6 ms
5,248 KB |
testcase_11 | AC | 6 ms
5,248 KB |
testcase_12 | AC | 5 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 1 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | AC | 2 ms
5,248 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 1 ms
5,248 KB |
testcase_27 | AC | 2 ms
5,248 KB |
testcase_28 | AC | 1 ms
5,248 KB |
testcase_29 | AC | 1 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 <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 998244353; // constexpr int MOD = 1000000007; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; template <typename T, bool IS_MINIMIZED = true> struct LiChaoTree { struct Line { T a, b; explicit Line(const T a, const T b) : a(a), b(b) {} T f(const T x) const { return a * x + b; } }; explicit LiChaoTree(const std::vector<T>& xs_, const T inf) : n(1), xs(xs_) { std::sort(xs.begin(), xs.end()); xs.erase(std::unique(xs.begin(), xs.end()), xs.end()); assert(xs.size() > 0); n = std::bit_ceil(xs.size()); const T xs_back = xs.back(); xs.resize(n, xs_back); dat.assign(n << 1, Line(0, inf)); } void add(T a, T b) { if constexpr (!IS_MINIMIZED) { a = -a; b = -b; } Line line(a, b); add(&line, 1, 0, n); } void add(T a, T b, T left, T right) { if constexpr (!IS_MINIMIZED) { a = -a; b = -b; } for (int len = 1, node_l = std::distance( xs.begin(), std::lower_bound(xs.begin(), xs.end(), left)), node_r = std::distance( xs.begin(), std::lower_bound(xs.begin(), xs.end(), right)), l = node_l + n, r = node_r + n; l < r; l >>= 1, r >>= 1, len <<= 1) { if (l & 1) { Line line(a, b); add(&line, l++, node_l, node_l + len); node_l += len; } if (r & 1) { Line line(a, b); node_r -= len; add(&line, --r, node_r, node_r + len); } } } T query(const T x) const { int node = n + std::distance(xs.begin(), std::lower_bound(xs.begin(), xs.end(), x)); T res = dat[node].f(x); while (node >>= 1) { if (dat[node].f(x) < res) res = dat[node].f(x); } return IS_MINIMIZED ? res : -res; } private: int n; std::vector<T> xs; std::vector<Line> dat; void add(Line* line, int node, int left, int right) { const bool flag_l = dat[node].f(xs[left]) <= line->f(xs[left]); const bool flag_r = dat[node].f(xs[right - 1]) <= line->f(xs[right - 1]); if (flag_l && flag_r) return; if (!flag_l && !flag_r) { std::swap(dat[node], *line); return; } const int mid = std::midpoint(left, right); if (line->f(xs[mid]) < dat[node].f(xs[mid])) std::swap(dat[node], *line); if (line->f(xs[left]) <= dat[node].f(xs[left])) { add(line, node << 1, left, mid); } else { add(line, (node << 1) + 1, mid, right); } } }; int main() { int a, q; cin >> a >> q; vector<int> s(q, -1), t(q); vector<ll> xs; xs.reserve(q); REP(i, q) { int type; cin >> type; if (type == 1) { cin >> s[i] >> t[i]; } else if (type == 2) { cin >> t[i]; xs.emplace_back(t[i]); } } ranges::sort(xs); xs.erase(unique(xs.begin(), xs.end()), xs.end()); LiChaoTree<ll, false> li_chao_tree(xs, LINF); REP(i, q) { if (s[i] == -1) { cout << max(li_chao_tree.query(t[i]) - 1LL * a * t[i] * t[i], 0LL) << '\n'; } else { li_chao_tree.add(1LL * a * (s[i] + t[i]), -1LL * a * s[i] * t[i]); } } return 0; }