結果

問題 No.2404 Vertical Throw Up
ユーザー amentorimaru
提出日時 2023-07-12 00:30:26
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,045 bytes
コンパイル時間 3,938 ms
コンパイル使用メモリ 125,056 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-14 06:49:47
合計ジャッジ時間 4,432 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 10
権限があれば一括ダウンロードができます

ソースコード

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) {
  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