結果

問題 No.3116 More and more teleporter
ユーザー aoblue2547
提出日時 2025-04-19 12:34:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 247 ms / 2,000 ms
コード長 4,605 bytes
コンパイル時間 6,125 ms
コンパイル使用メモリ 333,696 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-19 12:35:08
合計ジャッジ時間 9,835 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
template<class T> bool chmin(T& a, T b) { return a > b ? a = b, true : false; }
template<class T> bool chmax(T& a, T b) { return a < b ? a = b, true : false; }
template<typename T>
concept Iterable = requires(T t) { std::begin(t); std::end(t); };
template<typename T>
	requires Iterable<T> && (!is_same_v<T, string>)
ostream& operator<<(ostream& os, const T& container) { for (auto& element : container) os << element << ' '; return os; }
template<typename R>
	requires ranges::range<R> && (!is_same_v<decay_t<R>, string>) && (!is_same_v<decay_t<R>, const char*>)
ostream& operator<<(ostream& os, R&& range) { for (auto& element : range)os << element << ' '; return os; }
template<typename T>
	requires Iterable<T> && (!is_same_v<T, string>)
istream& operator>>(std::istream& is, T& container) { for (auto& e : container)is >> e; return is; }
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
template<class T = ll> struct Edge {
	int to;
	T weight;
	bool operator==(Edge e) { return this->to == e.to and this->weight == e.weight; }
	bool operator<(Edge e) { return this->to == e.to ? this->weight < e.weight : this->to < e.to; }
};
#ifdef _DEBUG
#define SHOW(n) {const auto& _ret = n; cerr << #n << ": " << _ret << endl;}
#define MSG(x) cerr << x << endl;
#else
#define SHOW(n)
#define MSG(x)
#endif

//AtCoder Library
#include <atcoder/all>
using namespace atcoder;
//using mint = modint998244353;
using mint = modint1000000007;
//using mint1 = dynamic_modint<0>;
//using mint = modint;
//mint::set_mod();
istream& operator>>(istream& is, mint& x) { ll r; is >> r; x = r; return is; }
ostream& operator<<(ostream& os, mint& x) { os << x.val(); return os; }

//boost
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
//using l3 = int128_t;


//LONG_MAX -> LLONG_MAX?

template<typename T = ll, T x_low = INT_MIN, T x_high = INT_MAX, T id = LLONG_MAX>
struct DynamicLiChaoTree {
	struct Line {
		T a, b;
		Line(T a, T b) : a(a), b(b) {}
		inline T get(T x)const { return a * x + b; }
	};

	struct Node {
		Line x;
		Node* l, * r;
		Node(const Line& x) : x{ x }, l{ nullptr }, r{ nullptr } {}
	};
	Node* root;

	DynamicLiChaoTree() : root { nullptr }{}

	Node* add_line(Node* t, Line& x, const T& l, const T& r, const T& x_l, const T& x_r) {
		if (not t)return new Node(x);
		T t_l = t->x.get(l), t_r = t->x.get(r);
		if (t_l <= x_l and t_r <= x_r)return t;
		if (t_l >= x_l and t_r >= x_r) {
			t->x = x;
			return t;
		}
		else {
			T m = (l + r) / 2;
			if (m == r)--m;
			//
			T t_m = t->x.get(m), x_m = x.get(m);
			if (t_m > x_m) {
				swap(t->x, x);
				if (x_l >= t_l) t->l = add_line(t->l, x, l, m, t_l, t_m);
				else t->r = add_line(t->r, x, m + 1, r, t_m + x.a, t_r);
			}
			else {
				if (t_l >= x_l)t->l = add_line(t->l, x, l, m, x_l, x_m);
				else t->r = add_line(t->r, x, m + 1, r, x_m + x.a, x_r);
			}
			return t;
		}
	}

	void add_line(const T& a, const T& b) {
		Line x(a, b);
		root = add_line(root, x, x_low, x_high, x.get(x_low), x.get(x_high));
	}

	Node* add_segment(Node* t, Line& x, const T& a, const T& b, const T& l, const T& r, const T& x_l, const T& x_r) {
		if (r < a or b < l)return t;
		if (a <= l and r <= b) {
			Line y{ x };
			return add_line(t, y, l, r, x_l, x_r);
		}
		if (t) {
			T t_l = t->x.get(l), t_r = t->x.get(r);
			if (t_l <= x_l and t_r <= x_r)return t;
		}
		else {
			t = new Node(Line(0, id));
		}
		T m = (l + r) / 2;
		if (m == r)--m;
		T x_m = x.get(m);
		t->l = add_segment(t->l, x, a, b, l, m, x_l, x_m);
		t->r = add_segment(t->r, x, a, b, m + 1, r, x_m + x.a, x_r);
		return t;
	}

	void add_segment(const T& l, const T& r, const T& a, const T& b) {
		Line x(a, b);
		root = add_segment(root, x, l, r - 1, x_low, x_high, x.get(x_low), x.get(x_high));
	}

	T query(const Node* t, const T& l, const T& r, const T& x)const {
		if (not t)return id;
		if (l == r)return t->x.get(x);
		T m = (l + r) / 2;
		if (m == r)--m;
		if (x <= m)return min(t->x.get(x), query(t->l, l, m, x));
		return min(t->x.get(x), query(t->r, m + 1, r, x));
	}

	T query(const T& x)const { return query(root, x_low, x_high, x); }
};

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);


	int n, q;
	cin >> n >> q;

	DynamicLiChaoTree t;

	t.add_segment(1, n + 1, 1, -1);


	while (q--) {
		int tt;
		cin >> tt;
		if (tt == 1) {
			int x;
			cin >> x;

			ll res = t.query(x);
			cout << res << endl;
		}
		else {
			ll x, c;
			cin >> x >> c;

			t.add_segment(1, x + 1, -1, x + c);
			t.add_segment(x, n + 1, 1, -x + c);
		}
	}



	return 0;
}
0