結果

問題 No.2404 Vertical Throw Up
コンテスト
ユーザー amentorimaru
提出日時 2023-07-04 00:53:05
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,271 bytes
コンパイル時間 1,793 ms
コンパイル使用メモリ 124,272 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-14 06:49:41
合計ジャッジ時間 4,069 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#include <numeric>

using namespace std;
using ll = long long;


class Rational {
public:
  Rational(ll nn = 0, ll dd = 1) {
    n = nn; d = dd; Reduction();
  }
  Rational operator+() const { return *this; }

  Rational& operator=(ll nn) { n = nn; d = 1; return *this; }
  Rational& operator = (const Rational& r) { n = r.n; d = r.d; return *this; }
  Rational& operator += (const Rational& r) { n = n * r.d + r.n * d; d *= r.d; Reduction(); return *this; }
  Rational& operator -= (const Rational& r) { n = n * r.d - r.n * d; d *= r.d; Reduction(); return *this; }
  Rational& operator *= (const Rational& r) { n *= r.n; d *= r.d; Reduction();  return *this; }
  Rational& operator /= (const Rational& r) { n *= r.d; d *= r.n; Reduction();  return *this; }

  bool operator ==(const Rational& r) { return n * r.d == r.n * d; }
  bool operator !=(const Rational& r) { return !(*this == r); }
  bool operator <(const Rational& r) {
    if (d == 0 && r.d == 0) return n < 0 && 0 < r.n;
    if (r.d == 0) return r.n > 0;
    if (d == 0) return n < 0;
    return n * r.d < r.n* d;
  }
  bool operator >(const Rational& r) {
    if (d == 0 && r.d == 0) return r.n < 0 && 0 < n;
    if (r.d == 0) return r.n < 0;
    if (d == 0) return n > 0;
    return n * r.d > r.n* d;
  }

  bool operator <=(const Rational& r) {
    return !(*this > r); 
  }
  bool operator >=(const Rational& r) { return !(*this < r); }

  void Reduction() {
    ll g = gcd(n, d);
    if (g == 0)return;
    if (d < 0)g *= -1;
    n /= g; d /= g;
  }
  // d is not negative
  ll n, d;
};

static Rational operator + (const Rational& l, const Rational& r) { return Rational(l) += r; }
static Rational operator - (const Rational& l, const Rational& r) { return Rational(l) -= r; }
static Rational operator * (const Rational& l, const Rational& r) { return Rational(l) *= r; }
static Rational operator / (const Rational& l, const Rational& r) { return Rational(l) /= r; }
static bool operator < (const Rational& l, const Rational& r) { return Rational(l) < r; }
static bool operator > (const Rational& l, const Rational& r) { return Rational(l) > r; }

int main() {
  ll a, q;
  cin >> a >> q;
  set<tuple<Rational, ll, ll>> vxy;
  set<tuple<ll, ll, Rational>> xyv;
  ll minf = -3e18;
  for (ll qs = 0; qs < q; qs++) {
    ll qq;
    cin >> qq;
    if (qq == 1) {
      ll s, t;
      cin >> s >> t;
      ll x = s + t;
      ll y = -s * t;
      auto erlast = xyv.lower_bound(make_tuple(x, minf, minf));
      ll lx = -1, ly = -1;
      Rational lv = -1;
      if (erlast != xyv.end()) {
        auto [bx, by, bv] = *erlast;
        if (x * bv + y <= bx * bv + by) {
          continue;
        }
        lx = bx; ly = by; lv = Rational(by - y, x - bx);
        while (1) {          
          erlast++;
          if (erlast == xyv.end()) {
            break;
          }
          auto [xx, yy, vv] = *erlast;
          if (x * vv + y < xx * vv + yy) {
            break;
          }
          if (x * vv + y == xx * vv + yy) {
            lx = -1; ly = -1; lv = -1;
            break;
          }
          lx = xx; ly = yy; lv = Rational(yy - y, x - xx);
        }
      }
      Rational fv = 0;
      auto erfirst = xyv.lower_bound(make_tuple(x, minf, minf));
      while (1) {
        if (erfirst == xyv.begin()) {
          fv = 0;
          break;
        }
        erfirst--;
        auto [xx, yy, vv] = *erfirst;
        if (x * vv + y < xx * vv + yy) {
          fv = Rational(yy - y, x - xx);
          erfirst++;
          break;
        }
      }
      for (auto eit = erfirst; eit != erlast; eit++) {
        auto [ex, ey, ev] = *eit;
        vxy.erase(make_tuple(ev, ex, ey));
      }
      xyv.erase(erfirst, erlast);
      xyv.emplace(x, y, fv);
      vxy.emplace(fv, x, y);
      if (lv >= 0) {
        xyv.emplace(lx, ly, lv);
        vxy.emplace(lv, lx, ly);
      }
    } 
    else {
      ll t;
      cin >> t;
      auto it = vxy.lower_bound(make_tuple(Rational(t), minf, minf));
      if (it == vxy.begin()) {
        cout << "0\n";
        continue;
      }
      it--;
      auto [vv, xx, yy] = *it;
      ll ans = -a * t * t + a * xx * t + a * yy;
      cout << max(ans, 0LL) << "\n";
    }
  }
  return 0;
}
0