結果

問題 No.2404 Vertical Throw Up
コンテスト
ユーザー achapi
提出日時 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

ソースコード

diff # 

#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';
		}
	}
}
0