結果

問題 No.3116 More and more teleporter
ユーザー eiya5498513
提出日時 2025-04-20 12:33:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 6,765 bytes
コンパイル時間 3,974 ms
コンパイル使用メモリ 218,676 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-20 12:34:02
合計ジャッジ時間 5,351 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>
#ifdef _MSC_VER
#pragma warning( push )
#pragma warning( disable : 26450 )
#pragma warning( disable : 26451 )
#pragma warning( disable : 26498 )
#pragma warning( disable : 4459 )
#endif
#include <atcoder/all>
#ifdef _MSC_VER
#pragma warning( pop )
#endif

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;


#if 0
// 定数 H
constexpr uint32_t H0[] = {
	0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
};

// 定数 K
constexpr uint32_t K[] = {
	0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
	0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
	0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
	0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
	0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
	0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
	0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
	0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};
#if 0
void func()
{
	// メッセージを N 個のメッセージブロック M^(0), ..., M^(N) に分割
	auto N = 1; // N = 1
	uint32_t W = [];
	uint32_t H[8] = {};
	for (let i = 0; i < 8; i++) {
		H[i] = H0[i];
	}

	// 各メッセージブロックに対して処理
	for (int t = 0; t < 64; t++) {
		if (t < 16) {
			// W[t] のスタートライン
			let p = (i - 1) * 64 + t * 4;
			// 8 ビットずつ左につめて、32 ビットの M_t^(i) を作成.
			W[t] = (msg[p] << 24) + (msg[p + 1] << 16) + (msg[p + 2] << 8) + msg[p + 3];
			// W[0] = 0x48656c6c (最初の4バイト: "Hell")
			// W[1] = 0x6f800000 (次の4バイト: "o" + padding)
			// W[2] から W[14] = 0x00000000 (padding)
			// W[15] = 0x00000028 (メッセージ長: 40)
		}
		else {
			W[t] = (sigma1(W[t - 2]) + W[t - 7] + sigma0(W[t - 15]) + W[t - 16]) & 0xffffffff;
		}
	}

	uint32_t a = H[0];
	uint32_t b = H[1];
	uint32_t c = H[2];
	uint32_t d = H[3];
	uint32_t e = H[4];
	uint32_t f = H[5];
	uint32_t g = H[6];
	uint32_t h = H[7];

	for (let t = 0; t < 64; t++) {
		let T1 = (h + SIGMA1(e) + Ch(e, f, g) + K[t] + W[t]) & 0xffffffff;
		let T2 = (SIGMA0(a) + Maj(a, b, c)) & 0xffffffff;
		next_h = g;
		next_g = f;
		next_f = e;
		next_e = (d + T1) & 0xffffffff;
		next_d = c;
		next_c = b;
		next_b = a;
		next_a = (T1 + T2) & 0xffffffff;

		h = next_h;
		g = next_g;
		f = next_f;
		e = next_e;
		d = next_d;
		c = next_c;
		b = next_b;
		a = next_a;
	}

	// ハッシュ値を符号なし32ビット整数に変換
	H[0] = a + H[0];
	H[1] = b + H[1];
	H[2] = c + H[2];
	H[3] = d + H[3];
	H[4] = e + H[4];
	H[5] = f + H[5];
	H[6] = g + H[6];
	H[7] = h + H[7];
}
#endif

// 1. ビット操作に使う関数
// 1-1. 右に n ビット巡回
uint32_t ROTR(uint32_t x, uint32_t n) {
	return (x >> n) | (x << (32 - n));
}

// 1-2. 右に nビットシフト
uint32_t SHR(uint32_t x, uint32_t n) {
	return x >> n;
}


// 2. SHA256 で使用する 6つの関数
// 2-1. Choose
uint32_t Ch(uint32_t x, uint32_t y, uint32_t z) {
	return (x & y) ^ (~x & z);
}

// 2-2. Majority
uint32_t Maj(uint32_t x, uint32_t y, uint32_t z) {
	return (x & y) ^ (x & z) ^ (y & z);
}

// 2-3
uint32_t sigma0(uint32_t x) {
	return ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3);
}

// 2-4
uint32_t sigma1(uint32_t x) {
	return ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10);
}

// 2-5
uint32_t SIGMA0(uint32_t x) {
	return ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22);
}

// 2-6
uint32_t SIGMA1(uint32_t x) {
	return ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25);
}


void decode()
{
	uint32_t a = 0 - H[0];
	uint32_t b = 0 - H[1];
	uint32_t c = 0 - H[2];
	uint32_t d = 0 - H[3];
	uint32_t e = 0 - H[4];
	uint32_t f = 0 - H[5];
	uint32_t g = 0 - H[6];
	uint32_t h = 0 - H[7];

	uint32_t W[64] = {};


	for (int t = 63; t >= 0; --t)
	{
		// (T1 + T2)  = a;
		// (prev_d + T1) = e;
		const auto prev_a = b;
		const auto prev_b = c;
		const auto prev_c = d;
		const auto prev_e = f;
		const auto prev_f = g;
		const auto prev_g = h;
		const auto T2 = SIGMA0(prev_a) + Maj(prev_a, prev_b, prev_c);
		const auto T1 = a - T2; // (T1 + T2)  = a;
		const auto prev_d = e - T1; // (prev_d + T1) = e;
		W[t] + prev_h = T1 - (SIGMA1(prev_e) + Ch(prev_e, prev_f, prev_g) + K[t]);


		h = prev_h;
		g = prev_g;
		f = prev_f;
		e = prev_e;
		d = prev_d;
		c = prev_c;
		b = prev_b;
		a = prev_a;
	}
	assert(a == H[0]);
	assert(b == H[1]);
	assert(c == H[2]);
	assert(d == H[3]);
	assert(e == H[4]);
	assert(f == H[5]);
	assert(g == H[6]);
	assert(h == H[7]);

	std::string msg;
	for (int t = 0; t < 16; t++) {
		msg += char((W[t] >> 24) & 0xff);
		msg += char((W[t] >> 16) & 0xff);
		msg += char((W[t] >> 8) & 0xff);
		msg += char((W[t] >> 0) & 0xff);
	}
	std::cout << msg;

}
#endif


int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	int64_t N, Q;
	in >> N >> Q;

	std::map<int32_t, int32_t> tel;
	tel[1] = 0;

	while (Q-- > 0)
	{
		int32_t type;
		in >> type;

		int32_t x;
		in >> x;

		auto right = tel.upper_bound(x);
		auto left = right; --left;
		auto min_c = left->second + (x - left->first);
		if (right != tel.end()) {
			min_c = std::min(min_c, right->second + (right->first - x));
		}

		if (type == 1) {
			out << min_c << '\n';
		}
		else
		{
			int32_t new_c;
			in >> new_c;

			if (new_c < min_c) {

				tel[x] = new_c;

				//左削除
				{
					left = --tel.lower_bound(x);
					auto toleft_new_c = new_c + (x - left->first);
					while (toleft_new_c < left->second) {
						left = tel.erase(left);
						--left;
						toleft_new_c = new_c + (x - left->first);
					}
				}
				//右削除
				if (right != tel.end()) {
					right = tel.upper_bound(x);
					auto toright_new_c = new_c + (right->first - x);
					while (right != tel.end() && toright_new_c < right->second) {
						right = tel.erase(right);
						if (right != tel.end()) {
							toright_new_c = new_c + (right->first - x);
						}
					}
				}
			}


		}
	}

}
#endif
0