結果

問題 No.3116 More and more teleporter
ユーザー みどりむし🦠
提出日時 2025-04-20 04:19:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,170 ms / 2,000 ms
コード長 1,219 bytes
コンパイル時間 3,129 ms
コンパイル使用メモリ 281,988 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-20 04:19:44
合計ジャッジ時間 14,112 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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