結果

問題 No.2404 Vertical Throw Up
ユーザー 👑 amentorimaruamentorimaru
提出日時 2023-07-12 00:30:26
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,045 bytes
コンパイル時間 2,482 ms
コンパイル使用メモリ 89,332 KB
実行使用メモリ 4,356 KB
最終ジャッジ日時 2023-10-12 07:40:06
合計ジャッジ時間 4,734 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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