結果

問題 No.3116 More and more teleporter
ユーザー shibh308
提出日時 2025-04-19 02:44:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,461 bytes
コンパイル時間 2,317 ms
コンパイル使用メモリ 206,840 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-19 02:44:18
合計ジャッジ時間 6,136 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include "atcoder/all"

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")

using namespace std;

using i64 = long long;


void solve(){
  int n, q;
  cin >> n >> q;

  std::map<int,i64> tel;
  tel.emplace(0, 0);

  for(int i = 0; i < q; ++i){
    int ty;
    cin >> ty;
    if(ty == 1){
      int x;
      cin >> x;
      --x;
      i64 cost = 1e18;
      auto it = tel.lower_bound(x);
      if(it != tel.end()){
        cost = min(cost, abs(it->first - x) + it->second);
      }
      auto prev_it = prev(it);
      cost = min(cost, abs(prev_it->first - x) + prev_it->second);
      cout << cost << endl;
    }
    else{
      int x;
      i64 c;
      cin >> x >> c;
      --x;
      auto it = tel.lower_bound(x);
      bool fl = true;
      while(it != tel.end()){
        if(abs(it->first - x) + c < it->second){
          it = tel.erase(it);
        }
        else if(abs(it->first - x) + it->second <= c){
          fl = false;
          break;
        }
        else{
          break;
        }
      }
      it = prev(tel.upper_bound(x));
      while(it != tel.begin()){
        if(abs(it->first - x) + c < it->second){
          it = tel.erase(it);
          --it;
        }
        else if(abs(it->first - x) + it->second <= c){
          fl = false;
          break;
        }
        else{
          break;
        }
      }
      if(fl){
        tel.emplace(x, c);
      }
    }
  }
}

signed main(){
  solve();
}
0