This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
#define IGNORE #define PROBLEM "https://atcoder.jp/contests/abc127/tasks/abc127_f" #include <cstdio> #include <cassert> #include "../../../structure/slope_trick.cpp" using ll = long long int; int main() { int Q; scanf("%d", &Q); SlopeTrick<ll> slope; while(Q--) { int type; scanf("%d", &type); if(type == 1) { ll a, b; scanf("%lld%lld", &a, &b); slope.addAbsFunc(a); slope.addConstFunc(b); } if(type == 2) { ll minF = slope.getMinVal(); ll lb, ub; bool isLbInfty, isUbInfty; slope.getArgminInterval(lb, isLbInfty, ub, isUbInfty); assert(!isLbInfty); printf("%lld %lld\n", lb, minF); } } return 0; }
#line 1 "verifying_test/AtCoder/ABC127/ABC127_F_slope_trick.test.cpp" #define IGNORE #define PROBLEM "https://atcoder.jp/contests/abc127/tasks/abc127_f" #include <cstdio> #include <cassert> #line 1 "structure/slope_trick.cpp" #include <queue> #include <vector> #include <algorithm> #line 8 "structure/slope_trick.cpp" // 区分線形凸関数 f: Tp -> Tp を管理 template <typename Tp = int> struct SlopeTrick { SlopeTrick(Tp minF = 0) : minF(minF), addL((Tp)0), addR((Tp)0) {} // 定数関数 a を加算: O(1) void addConstFunc(Tp a) { minF += a; } // f(x) = (x - a)+ = max(0, x - a) を加算: O(log N) void addXmaFunc(Tp a); // f(x) = (a - x)+ = max(0, a - x) を加算: O(log N) void addAmxFunc(Tp a); // f(x) = |x - a| を加算: O(log N) void addAbsFunc(Tp a); // 左側累積 min (\min_{y \leq x} f(y)) を取る: O(1) void accumulateLeft() { ptsR = decltype(ptsR)(); } // 右側累積 min (\min_{y \geq x} f(y)) を取る: O(1) void accumulateRight() { ptsL = decltype(ptsL)(); } // 平行移動 すなわち g(x) = f(x - a) のように更新: O(1) void applyTranslation(Tp a); // スライド最小値 すなわち g(x) = \min_{y \in [x-b, x-a]} f(y) のように更新: O(1) void applySlidingWindow(Tp a, Tp b); // 関数の最小値を返す: O(1) Tp getMinVal() const { return minF; } // 関数の値が最小になるような x の範囲を返す: O(1) void getArgminInterval(Tp& lb, bool& isLbInfty, Tp& ub, bool& isUbInfty) const; private: // pt の値 v について、その真の値: L の場合 v + addL, R の場合 v + addR Tp minF, addL, addR; std::priority_queue<Tp> ptsL; std::priority_queue<Tp, std::vector<Tp>, std::greater<Tp>> ptsR; }; template <typename Tp> void SlopeTrick<Tp>::addXmaFunc(Tp a) { if(ptsL.size()) { minF += std::max((Tp)0, (ptsL.top() + addL) - a); } ptsL.emplace(a - addL); Tp maxPt = ptsL.top() + addL; ptsL.pop(); ptsR.emplace(maxPt - addR); } template <typename Tp> void SlopeTrick<Tp>::addAmxFunc(Tp a) { if(ptsR.size()) { minF += std::max((Tp)0, a - (ptsR.top() + addR)); } ptsR.emplace(a - addR); Tp minPt = ptsR.top() + addR; ptsR.pop(); ptsL.emplace(minPt - addL); } template <typename Tp> void SlopeTrick<Tp>::addAbsFunc(Tp a) { addXmaFunc(a); addAmxFunc(a); } template <typename Tp> void SlopeTrick<Tp>::applyTranslation(Tp a) { applySlidingWindow(a, a); } template <typename Tp> void SlopeTrick<Tp>::applySlidingWindow(Tp a, Tp b) { assert(a <= b); addL += a; addR += b; } template <typename Tp> void SlopeTrick<Tp>::getArgminInterval(Tp& lb, bool& isLbInfty, Tp& ub, bool& isUbInfty) const { if(ptsL.size()) { lb = ptsL.top() + addL; isLbInfty = false; } else { isLbInfty = true; } if(ptsR.size()) { ub = ptsR.top() + addR; isUbInfty = false; } else { isUbInfty = true; } } #line 7 "verifying_test/AtCoder/ABC127/ABC127_F_slope_trick.test.cpp" using ll = long long int; int main() { int Q; scanf("%d", &Q); SlopeTrick<ll> slope; while(Q--) { int type; scanf("%d", &type); if(type == 1) { ll a, b; scanf("%lld%lld", &a, &b); slope.addAbsFunc(a); slope.addConstFunc(b); } if(type == 2) { ll minF = slope.getMinVal(); ll lb, ub; bool isLbInfty, isUbInfty; slope.getArgminInterval(lb, isLbInfty, ub, isUbInfty); assert(!isLbInfty); printf("%lld %lld\n", lb, minF); } } return 0; }