結果

問題 No.2404 Vertical Throw Up
ユーザー achapiachapi
提出日時 2023-08-04 22:47:20
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 125 ms / 2,000 ms
コード長 2,839 bytes
コンパイル時間 4,900 ms
コンパイル使用メモリ 266,608 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-22 21:06:51
合計ジャッジ時間 6,923 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 100 ms
5,376 KB
testcase_04 AC 80 ms
5,376 KB
testcase_05 AC 124 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 125 ms
5,376 KB
testcase_08 AC 98 ms
5,376 KB
testcase_09 AC 78 ms
5,376 KB
testcase_10 AC 22 ms
5,376 KB
testcase_11 AC 22 ms
5,376 KB
testcase_12 AC 15 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 3 ms
5,376 KB
testcase_15 AC 3 ms
5,376 KB
testcase_16 AC 3 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 3 ms
5,376 KB
testcase_19 AC 3 ms
5,376 KB
testcase_20 AC 3 ms
5,376 KB
testcase_21 AC 4 ms
5,376 KB
testcase_22 AC 3 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 3 ms
5,376 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 3 ms
5,376 KB
testcase_27 AC 3 ms
5,376 KB
testcase_28 AC 3 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 3 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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