結果

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

ソースコード

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 --;
	int h1 = i1->second + std::abs(x - i1->first);
	int h2 = i2->second + std::abs(i2->first - x);
	return std::min(h1, h2);
}

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 = valleys.find(x) ++; itr != valleys.end();){
					if(height_at(itr->second) > itr->first){
						itr = valleys.erase(itr);
					}
					else break;
				}
				for(auto itr = valleys.find(x) --; itr != valleys.begin(); --itr){
					if(height_at(itr->second) > itr->first){
						itr = valleys.erase(itr);
					}
					else break;
				}
			}
		}
	}
}
0