結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー sig_256
提出日時 2025-04-20 01:23:15
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 262 ms / 2,000 ms
コード長 1,116 bytes
コンパイル時間 3,286 ms
コンパイル使用メモリ 92,716 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-20 01:23:23
合計ジャッジ時間 5,362 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <map>

std::map<int, int> valleys;

int height_at(int x){
	auto i1 = valleys.lower_bound(x); if(i1 != valleys.begin()) i1 --;
	auto i2 = valleys.lower_bound(x); if(i2 == valleys.end()) i2 --;
	auto i3 = valleys.upper_bound(x); if(i2 == valleys.end()) i2 --;
	int h1 = i1->second + std::abs(x - i1->first);
	int h2 = i2->second + std::abs(i2->first - x);
	int h3 = i3->second + std::abs(i3->first - x);
	return std::min(h1, std::min(h2, h3));
}

int main(){
	int N, Q;
	std::cin >> N >> Q;
	valleys[1] = 0;
	for(int q = 0, mode, x, c; q < Q; ++q){
		std::cin >> mode >> x;
		if(mode == 1){
			std::cout << height_at(x) << std::endl;
		}
		else{
			std::cin >> c;
			if(c < height_at(x)){
				valleys[x] = c;
				for(auto itr = std::next(valleys.find(x)); itr != valleys.end();){
					if(height_at(itr->first) < itr->second){
						itr = valleys.erase(itr);
					}
					else break;
				}
				for(auto itr = std::prev(valleys.find(x)); itr != valleys.begin(); --itr){
					if(height_at(itr->first) < itr->second){
						itr = valleys.erase(itr);
					}
					else break;
				}
			}
		}
	}
}
0