結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー みどりむし🦠
提出日時 2025-04-20 04:19:29
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 661 ms / 2,000 ms
コード長 1,219 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,384 ms
コンパイル使用メモリ 340,168 KB
実行使用メモリ 5,760 KB
最終ジャッジ日時 2026-07-10 01:27:00
合計ジャッジ時間 9,360 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

long constexpr INF64 = 1L << 60;

int main() {
	int n, q; std::cin >> n >> q;
	std::set<std::pair<int, long>> ps { { 0, 0 } };
	
	for(auto _ : std::views::iota(0, q)) {
		std::cerr << _ << " : " << ps.size() << "\n";

		int t, x; std::cin >> t >> x; --t, --x;
		
		auto get = [&](auto x) {
			long res = INF64;
			{
				auto itr = ps.lower_bound({ x, -INF64 });
				if(itr != ps.end()) {
					res = std::min(res, itr->second + std::abs(itr->first - x));
				}
			}
			{
				auto itr = ps.upper_bound({ x, -INF64 });
				if(itr != ps.begin()) {
					--itr;
					res = std::min(res, itr->second + std::abs(itr->first - x));
				}
			}
			return res;
		};
		
		if(t == 0) {
			std::cout << get(x) << "\n";
		}
		if(t == 1) {
			long c; std::cin >> c;
			
			if(get(x) <= c) continue;
			
			{
				auto itr = ps.lower_bound({ x, -INF64 });
				while(itr != ps.end()) {
					if(c + std::abs(itr->first - x) <= itr->second) itr = ps.erase(itr);
					else break;
				}
			}
			{
				auto itr = ps.upper_bound({ x, -INF64 });
				while(itr != ps.begin()) {
					--itr;
					if(c + std::abs(itr->first - x) <= itr->second) itr = ps.erase(itr);
					else break;
				}
			}

			ps.emplace(x, c);
		}
	}
}
0