#906759 (C++17) No.2404 Vertical Throw Up

提出ソース

結果

問題	No.2404 Vertical Throw Up
ユーザー	marc2825
提出日時	2023-08-22 05:42:15
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	108 ms / 2,000 ms
コード長	10,106 bytes
コンパイル時間	1,092 ms
コンパイル使用メモリ	111,500 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-05-09 11:38:32
合計ジャッジ時間	3,540 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	86 ms 6,940 KB
testcase_04	AC	73 ms 6,940 KB
testcase_05	AC	108 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	108 ms 6,940 KB
testcase_08	AC	83 ms 6,940 KB
testcase_09	AC	69 ms 6,940 KB
testcase_10	AC	20 ms 6,944 KB
testcase_11	AC	19 ms 6,940 KB
testcase_12	AC	13 ms 6,944 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	3 ms 6,944 KB
testcase_15	AC	3 ms 6,940 KB
testcase_16	AC	3 ms 6,944 KB
testcase_17	AC	3 ms 6,944 KB
testcase_18	AC	3 ms 6,940 KB
testcase_19	AC	3 ms 6,940 KB
testcase_20	AC	3 ms 6,940 KB
testcase_21	AC	3 ms 6,940 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	3 ms 6,940 KB
testcase_25	AC	2 ms 6,944 KB
testcase_26	AC	2 ms 6,944 KB
testcase_27	AC	3 ms 6,944 KB
testcase_28	AC	2 ms 6,940 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	2 ms 6,944 KB
testcase_31	AC	3 ms 6,940 KB
testcase_32	AC	2 ms 6,940 KB

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

コンパイルメッセージ

main.cpp:73: warning: "debug" redefined
   73 | #define debug(...) void(0)
      | 
main.cpp:68: note: this is the location of the previous definition
   68 | #define debug(x) void(0)
      |

ソースコード

raw source code

#include <iostream>
#include <iomanip>
#include <cassert>
#include <limits>
#include <vector>

#include <set>
#include <deque>
#include <cmath>

#include <algorithm>


using namespace std;

using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vld = vector<ld>;
using vd = vector<double>;
using vvd = vector<vd>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;
using pii = pair<int, int>;
using pcc = pair<char, char>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using pldld = pair<ld,ld>;
using vpii = vector<pii>;
using vpll = vector<pll>;
 
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

#define rep(i, n) for (ll i = 0; i < ll(n); i++)
#define repback(i, n) for (ll i = n-1; i >= 0; i--)
#define REP(i, a, b) for (ll i = a; i < ll(b); i++)
#define REPBACK(i, a, b) for (ll i = a-1; i >= ll(b); i--)
#define all(x) (x).begin(), (x).end()
#define UNIQUE(A) A.erase(unique(all(A)), A.end()) // sortしてから使う
#define include(y, x, H, W) (0 <= x && x < W && 0 <= y && y < H)
#define square(x) (x) * (x)
#define pb push_back
#define eb emplace_back
#define EPS (1e-10)
#define equals(a,b) (fabs((a) - (b)) < EPS)
#ifndef ONLINE_JUDGE
#define debug1(x) cout << "debug:" << (x) << endl
#define debug2(x, y) cout << "debug:" << (x) << " " << (y) << endl
#define debug3(x, y, z) cout << "debug:" << (x) << " " << (y) << " " << (z) << endl
#define debug4(x, y, z, w) cout << "debug:" << (x) << " " << (y) << " " << (z) << " " << (w) << endl
#define debug5(x, y, z, w, v) cout << "debug:" << (x) << " " << (y) << " " << (z) << " " << (w) << " " << (v) << endl
#define overload5(a, b, c, d, e, f, ...) f
#define debug(...) overload5(__VA_ARGS__, debug5, debug4, debug3, debug2, debug1)(__VA_ARGS__)
#define debug2C(x, y) cout << "debug:" << (x) << " : " << (y) << endl
#define debug3P(x, y, z) cout << "debug:" << (x) << ", " << (y) << " : " << (z) << endl
#define debug3C(x, y, z) cout << "debug:" << (x) << " : " << (y) << ", " << (z) << endl
#define debuga cerr << "a" << endl
#else
#define debug(x) void(0)
#define debug2(x, y) void(0)
#define debug3(x, y, z) void(0)
#define debug4(x, y, z, w) void(0)
#define debug5(x, y, z, w, v) void(0)
#define debug(...) void(0)
#define debug2C(x, y) void(0)
#define debug3P(x, y, z) void(0)
#define debug3C(x, y, z) void(0)
#define debuga void(0)
#define TIMER_START void(0)
#define TIMER_END void(0)
#define TIMECHECK void(0)
#endif

const long long INFL = 1000000000000000000ll;
const long long INFLMAX = numeric_limits< long long >::max(); // 9223372036854775807
const int INF = 1000000000;
const int INFMAX = numeric_limits< int >::max(); // 2147483647
const int mod1 = 1000000007;
const int mod2 = 998244353;
const vi dx1 = {1,0,-1,0};
const vi dy1 = {0,1,0,-1};
const vi dx2 = {0, 1, 1, 1, 0, -1, -1, -1, 0};
const vi dy2 = {1, 1, 0, -1, -1, -1, 0, 1, 1};
const char nl = '\n';

// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec) {
	os << "[";
	for (int i = 0; i<vec.size(); i++) {
		os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
	}
	os << "]";
	return os;
}
// pair出力
template<typename T, typename U>
ostream& operator << (ostream& os, pair<T, U>& pair_var) {
	os << "(" << pair_var.first << ", " << pair_var.second << ")";
	return os;
}

// ############################
// #                          #
// #    C O D E  S T A R T    #
// #                          #
// ############################ 


/// 直線 y = kx+m, p は不要な直線か？の判定 / クエリ処理における二分探索 に用いる値 (具体的には、傾き降順で次の直線との交点のx座標 = (y切片の差) / (傾きの差) )
template <typename T = long long>
struct Line {
    mutable T k, m, p; 
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(T x) const { return p < x; }

    T get_value(T x) const {
        return k * x + m;
    }
};

/// div(a,b) = (for doubles, use inf = 1/.0, div(a,b) = a/b)
template <typename T = long long>
T lc_inf() {
    return numeric_limits<T>::max();
}
template <>
long double lc_inf<long double>() {
    return 1 / .0;
}

template <typename T = long long>
T lc_div(T a, T b) { // クエリが整数ならfloored division でよい, considered negative
    return a / b - (((a ^ b) < 0) && (a % b));
}
template <>
long double lc_div(long double a, long double b) {
    return a / b;
}
template <>
double lc_div(double a, double b) {
    return a / b;
}


/// Convex Hull Trick
// 直線群 kx+m を管理（追加可能）、任意のxでの最大値/最小値取得クエリをそれぞれ O(log N) で処理可能 (N = 直線の数)
// Minimize でクエリの種類（最小/最大取得）を指定、MonotonicAdd で 追加する直線の傾きの単調性（max->降順/min->昇順）が保証されているか（単調なら線形時間に出来る）を指定
// 何をしてるかは Reference[3] がわかりやすい（グラフをイメージすると更によい）
template <typename T, bool Minimize = true, bool MonotonicAdd = false>
class ConvexHullTrick : multiset<Line<T>, less<> > {
    private:
        using base = multiset<Line<T>, less<> >;
        using base::begin, base::end, base::insert, base::erase, base::rbegin, base::rend;
        using base::empty, base::lower_bound;
        const T inf = lc_inf<T>();
        deque<Line<T> > deq;

        /// 直線bが不要かどうかを判定（要するに直線bが凸包を構成しているかを判定しており、これで交点pのx座標の単調性が保たれる）
        bool noneed(const Line<T> &a, const Line<T> &b, const Line<T> &c) { // TODO : オーバーフロー関連
            if((c.k != b.k && abs(b.m - a.m) >= inf / abs(c.k - b.k)) || (c.m != b.m && abs(b.k - a.k) >= inf / abs(c.m - b.m))) return lc_div(b.m - a.m, a.k - b.k) >= lc_div(c.m - b.m, b.k - c.k);
            else return ((b.m - a.m) * (c.k - b.k)) >= ((b.k - a.k) * (c.m - b.m));
        }

        /// 直線a,bとの交点のx座標(a->p)を計算してから、直線bが不要かどうかを判定
        bool calc_intersect_noneed(typename base::iterator a, typename base::iterator b) {
            if (b == end()) {
                a->p = inf;
                return false;
            }
            if (a->k == b->k) a->p = (a->m > b->m ? inf : -inf);
            else a->p = lc_div(b->m - a->m, a->k - b->k);
            return a->p >= b->p;
        }

        /// multiset -> deque に格納（単調クエリ用）
        void build_deque() {
            assert(!empty());
            auto it = rbegin();
            while(it != rend()) {
                deq.push_back(*it);
                it++;
            }
        }

    public:
        /// 直線 kx+m を追加（同時に不要な直線たちは削除される）
        void add(T k, T m) {
            if (Minimize) k = -k, m = -m;
            
            if(!MonotonicAdd) {
                auto cur = insert({k, m, 0});
                auto nxt = cur; nxt++;
                while (calc_intersect_noneed(cur, nxt)) nxt = erase(nxt);

                auto prev = cur;
                if (prev != begin() && calc_intersect_noneed(--prev, cur)) {
                    cur = erase(cur);
                    calc_intersect_noneed(prev, cur);
                }
                while ((cur = prev) != begin() && (--prev)->p >= cur->p) calc_intersect_noneed(prev, erase(cur));
            }
            else {
                Line<T> l = {k, m, 0};
                int sz = deq.size();
                while ((sz = deq.size()) >= 2 && noneed(deq[sz-2], deq[sz-1], l)) deq.pop_back();
                deq.push_back(l);
            }
        }

        /// 直線群の x における 最小値/最大値 を取得
        // O(log N)
        T query(T x) {
            T value;
            if (!MonotonicAdd) {
                assert(!empty());
                auto l = *lower_bound(x);
                value = l.get_value(x);
            }
            else {
                assert(!deq.empty());
                int ng = -1, ok = (int)deq.size() - 1;
                while(ok - ng > 1) {
                    int mid = (ok + ng) / 2;
                    if(deq[mid].get_value(x) <= deq[mid + 1].get_value(x)) ng = mid;
                    else ok = mid;
                }
                value = deq[ok].get_value(x);
            }
            return (Minimize ? -value : value);
        }

        /// xが(max->降順、min->昇順) という条件で、直線群の x における 最小値/最大値 を取得
        // O(N) 、破壊的操作
        T query_monotonic(T x) {
            if(!MonotonicAdd && deq.empty()) build_deque();
            assert(!deq.empty());
            
            T value = deq.front().get_value(x);
            while (deq.size() >= 2 && (value <= (deq[1].get_value(x)))) {
                deq.pop_front();
                value = deq.front().get_value(x);
            }  
            return (Minimize ? -value : value);
        }
};

template <typename T>
using CHT_min = ConvexHullTrick<T, true, false>;
template <typename T>
using CHT_min_monotonicadd = ConvexHullTrick<T, true, true>;
template <typename T>
using CHT_max = ConvexHullTrick<T, false, false>;
template <typename T>
using CHT_max_monotonicadd = ConvexHullTrick<T, false, true>;


int main() {
    // cin.tie(0);
    // ios_base::sync_with_stdio(false);
    // cout << fixed << setprecision(15);

    ll a; cin >> a;
    CHT_max<ll> CHT;
    int Q; cin >> Q;
    while(Q--) {
        int q; cin >> q;
        if(q == 1) {
            ll s,t; cin >> s >> t;
            CHT.add(a*(s+t), -a*s*t);
        }
        else {
            ll t; cin >> t;

            cout << max(0ll, -a*t*t + CHT.query(t)) << nl;
        }
    }

}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード