結果

問題 No.2404 Vertical Throw Up
コンテスト
ユーザー amentorimaru
提出日時 2023-07-12 00:44:28
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 107 ms / 2,000 ms
コード長 2,345 bytes
コンパイル時間 1,242 ms
コンパイル使用メモリ 125,952 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 19:14:59
合計ジャッジ時間 2,930 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;
using ll = long long;

bool check(ll a1, ll b1, ll a2, ll b2, ll a3, ll b3) {
  ll c = 1e9;
  ll a21 = a2 - a1;
  ll a32 = a3 - a2;
  ll b21 = b2 - b1;
  ll b32 = b3 - b2;
  ll le9 = b32 / c * a21 + b32 % c * a21 / c;
  ll re9 = b21 / c * a32 + b21 % c * a32 / c;
  if (le9 < re9)
    return true;
  if (le9 > re9)
    return false;
  return b32 % c * a21 % c < b21% c* a32% c;
  return (a2 - a1) * (b3 - b2) < (b2 - b1) * (a3 - a2);
}

int main() {
  ll a, q;
  cin >> a >> q;
  set<pair<ll, ll>> ch;
  for (ll qs = 0; qs < q; qs++) {
    ll qq;
    cin >> qq;
    if (qq == 1) {
      ll s, t;
      cin >> s >> t;
      pair<ll, ll> add = make_pair(s + t, - s * t);
      //pair<ll, ll> add = make_pair(s, t);
      auto it = ch.lower_bound(add);
      if (it != ch.begin() && it != ch.end()) {
        auto ita = it;
        ita--;
        if (!check(ita->first, ita->second, add.first, add.second, it->first, it->second)) {
          continue;
        }
      }
      it = ch.insert(add).first;
      while (1) {
        auto it2 = it;
        auto it3 = it;
        it2++;
        it3++;
        if (it2 == ch.end())
          break;
        it3++;
        if (it3 == ch.end())
          break;
        if (check(it->first, it->second, it2->first, it2->second, it3->first, it3->second))
          break;
        ch.erase(it2);
      }
      while (1) {
        auto it2 = it;
        auto it3 = it;
        if (it == ch.begin())
          break;
        it2--;
        it3--;
        if (it2 == ch.begin())
          break;
        it3--;
        if (check(it3->first, it3->second, it2->first, it2->second, it->first, it->second))
          break;
        ch.erase(it2);
      }
    }
    else {
      ll t;
      cin >> t;
      while (!ch.empty()) {
        auto it = ch.begin();
        auto it2 = it;
        it2++;
        if (it2 == ch.end())
          break;
        if (t * it->first + it->second <= t * it2->first + it2->second)
          ch.erase(it);
        else
          break;
      }
      if (ch.empty()) {
        cout << "0\n";
      }
      else {
        auto it = ch.begin();
        ll ans = a * (-t * t + it->first * t + it->second);
        cout << max(ans, 0LL) << "\n";
      }
    }
  }
  return 0;
}
0