結果
| 問題 |
No.2404 Vertical Throw Up
|
| コンテスト | |
| ユーザー |
 marc2825
|
| 提出日時 | 2023-08-22 05:42:15 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 106 ms / 2,000 ms |
| コード長 | 10,106 bytes |
| コンパイル時間 | 990 ms |
| コンパイル使用メモリ | 110,056 KB |
| 最終ジャッジ日時 | 2025-02-16 12:11:28 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 |
コンパイルメッセージ
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)
|
ソースコード
#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;
}
}
}