結果
問題 | No.2404 Vertical Throw Up |
ユーザー |
|
提出日時 | 2023-08-04 22:47:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 2,839 bytes |
コンパイル時間 | 4,014 ms |
コンパイル使用メモリ | 265,404 KB |
最終ジャッジ日時 | 2025-02-15 23:07:31 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
コンパイルメッセージ
main.cpp: In member function ‘void CHT2::print()’: main.cpp:16:51: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘ll’ {aka ‘long double’} [-Wformat=] 16 | cout << "S : "; for (auto it : S) printf("(%lld,%lld)", it.a, it.b); puts(""); | ~~~^ ~~~~ | | | | | ll {aka long double} | long long int | %Lf main.cpp:16:56: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 3 has type ‘ll’ {aka ‘long double’} [-Wformat=] 16 | cout << "S : "; for (auto it : S) printf("(%lld,%lld)", it.a, it.b); puts(""); | ~~~^ ~~~~ | | | | long long int ll {aka long double} | %Lf main.cpp:17:51: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘ll’ {aka ‘long double’} [-Wformat=] 17 | cout << "C : "; for (auto it : C) printf("(%lld,%lld)", it.n, it.d); puts(""); | ~~~^ ~~~~ | | | | | ll {aka long double} | long long int | %Lf main.cpp:17:56: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 3 has type ‘ll’ {aka ‘long doubl
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; typedef long double ll; const ll INF = LLONG_MAX; struct CHT2 { CHT2() { // 番兵 S.insert({L(INF,0), L(-INF,0)}); C.insert(cp(L(INF,0),L(-INF,0))); } // for debug void print() { cout << "S : "; for (auto it : S) printf("(%lld,%lld)", it.a, it.b); puts(""); cout << "C : "; for (auto it : C) printf("(%lld,%lld)", it.n, it.d); puts(""); } // |ab| < LLONG_MAX/4 ??? void add(ll a, ll b) { const L p(a,b); It pos = S.insert(p).first; if (check(*it_m1(pos), p, *it_p1(pos))) { // 直線(a,b)が不要 S.erase(pos); return; } C.erase(cp(*it_m1(pos), *it_p1(pos))); { // 右方向の削除 It it = it_m1(pos); while(it!=S.begin() && check(*it_m1(it), *it, p)) --it; C_erase(it, it_m1(pos)); S.erase(++it,pos); pos = S.find(p); } { // 左方向の削除 It it = it_p1(pos); while(it_p1(it)!=S.end() && check(p,*it, *it_p1(it))) ++it; C_erase(++pos, it); S.erase(pos, it); pos = S.find(p); } C.insert(cp(*it_m1(pos), *pos)); C.insert(cp(*pos, *it_p1(pos))); } ll query(ll x) { const L &p = (--C.lower_bound(CP(x,1,L(0,0))))->p; return p.a*x + p.b; } private: template<class T> T it_p1(T a) { return ++a; } template<class T> T it_m1(T a) { return --a; } struct L { ll a, b; L(ll a, ll b) : a(a),b(b) {} bool operator<(const L &rhs) const { return a != rhs.a ? a > rhs.a : b < rhs.b; } }; struct CP { ll n,d; L p; CP(ll _n, ll _d, const L &p) : n(_n),d(_d),p(p) { if (d < 0) { n *= -1; d *= -1; } }; bool operator<(const CP &rhs) const { if (n == INF || rhs.n == -INF) return 0; if (n == -INF || rhs.n == INF) return 1; return n * rhs.d < rhs.n * d; } }; set<L> S; set<CP> C; typedef set<L>::iterator It; void C_erase(It a, It b) { for (It it=a; it!=b; ++it) C.erase(cp(*it, *it_p1(it))); } CP cp(const L &p1, const L &p2) { if (p1.a == INF) return CP(-INF,1,p2); if (p2.a == -INF) return CP(INF,1,p2); return CP(p1.b-p2.b, p2.a-p1.a, p2); } bool check(const L &p1, const L &p2, const L &p3) { if (p1.a==p2.a && p1.b <= p2.b) return 1; if (p1.a == INF || p3.a == -INF) return 0; return (p2.a-p1.a)*(p3.b-p2.b) >= (p2.b-p1.b)*(p3.a-p2.a); } }; int main() { long long a; cin >> a; int Q; cin >> Q; CHT2 cht; while (Q--){ int T; cin >> T; if (T == 1){ long long s, t; cin >> s >> t; long double b = a * (t * t - s * s); b /= t - s; long double c = s * (a * s - b); cht.add(-b, -c); } if (T == 2){ long long t; cin >> t; long long c = -1 * cht.query(t) - a * t * t; cout << max(0LL, c) << '\n'; } } }