結果

問題 No.2404 Vertical Throw Up
ユーザー ゆにぽけゆにぽけ
提出日時 2024-02-13 17:02:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 30 ms / 2,000 ms
コード長 4,362 bytes
コンパイル時間 1,130 ms
コンパイル使用メモリ 132,076 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-09-28 18:31:30
合計ジャッジ時間 2,843 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,820 KB
testcase_03 AC 23 ms
6,816 KB
testcase_04 AC 19 ms
6,816 KB
testcase_05 AC 30 ms
6,816 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 30 ms
6,820 KB
testcase_08 AC 23 ms
6,816 KB
testcase_09 AC 18 ms
6,816 KB
testcase_10 AC 7 ms
6,816 KB
testcase_11 AC 6 ms
6,816 KB
testcase_12 AC 5 ms
6,820 KB
testcase_13 AC 2 ms
6,816 KB
testcase_14 AC 2 ms
6,820 KB
testcase_15 AC 2 ms
6,816 KB
testcase_16 AC 2 ms
6,820 KB
testcase_17 AC 2 ms
6,816 KB
testcase_18 AC 2 ms
6,816 KB
testcase_19 AC 1 ms
6,820 KB
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 2 ms
6,820 KB
testcase_22 AC 2 ms
6,820 KB
testcase_23 AC 1 ms
6,816 KB
testcase_24 AC 2 ms
6,820 KB
testcase_25 AC 1 ms
6,816 KB
testcase_26 AC 2 ms
6,816 KB
testcase_27 AC 2 ms
6,816 KB
testcase_28 AC 2 ms
6,816 KB
testcase_29 AC 2 ms
6,816 KB
testcase_30 AC 2 ms
6,820 KB
testcase_31 AC 2 ms
6,816 KB
testcase_32 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <string>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <random>
#include <utility>
#include <functional>
using namespace std;
template<class T,T lower_limit,T upper_limit,T id>
struct LiChaoTree
{
	private:
	
	struct Line
	{
		T a,b;
		Line(T a,T b) : a(a),b(b) {}

		inline T eval(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;

	Node *add_line(Node *node,Line &x,const T &lower,const T &upper,const T &lower_value,const T &upper_value)
	{
		if(!node)
		{
			return new Node(x);
		}

		T node_lower_value = node -> x.eval(lower);
		T node_upper_value = node -> x.eval(upper);

		if(node_lower_value <= lower_value && node_upper_value <= upper_value)
		{
			return node;
		}
		else if(node_lower_value >= lower_value && node_upper_value >= upper_value)
		{
			node -> x = x;
			return node;
		}
		else
		{
			T mid = (lower + upper) / 2;

			if(mid == upper)
			{
				mid--;
			}

			T node_mid_value = node -> x.eval(mid),mid_value = x.eval(mid);

			T nxt_lower_value = lower_value;
			T nxt_mid_value = mid_value;
			T nxt_upper_value = upper_value;

			if(node_mid_value > mid_value)
			{
				swap(node -> x,x);
				swap(node_lower_value,nxt_lower_value);
				swap(node_mid_value,nxt_mid_value);
				swap(node_upper_value,nxt_upper_value);
			}

			if(node_lower_value >= nxt_lower_value)
			{
				node -> l = add_line(node -> l,x,lower,mid,nxt_lower_value,nxt_mid_value);
			}
			else
			{
				node -> r = add_line(node -> r,x,mid + 1,upper,nxt_mid_value + x.a,nxt_upper_value);
			}

			return node;
		}
	}

	Node *add_segment(Node *node,Line &x,const T &x_l,const T &x_r,const T &lower,const T &upper,const T &lower_value,const T &upper_value)
	{
		if(upper < x_l || x_r < lower)
		{
			return node;
		}
		if(x_l <= lower && upper <= x_r)
		{
			Line y = x;
			return add_line(node,y,lower,upper,lower_value,upper_value);
		}

		if(node)
		{
			T node_lower_value = node -> x.eval(lower);
			T node_upper_value = node -> x.eval(upper);
			
			if(node_lower_value <= lower_value && node_upper_value <= upper_value)
			{
				return node;
			}
		}
		else
		{
			node = new Node(Line(0,id));
		}

		T mid = (lower + upper) / 2;
		if(mid == upper)
		{
			mid--;
		}

		T mid_value = x.eval(mid);
		node -> l = add_segment(node -> l,x,x_l,x_r,lower,mid,lower_value,mid_value);
		node -> r = add_segment(node -> r,x,x_l,x_r,mid + 1,upper,mid_value + x.a,upper_value);
		return node;
	}

	T query(const Node *node,const T &x_l,const T &x_r,const T &x) const
	{
		if(!node)
		{
			return id;
		}

		T res = node -> x.eval(x);

		if(x_l == x_r)
		{
			return res;
		}

		T x_m = (x_l + x_r) / 2;
		if(x_m == x_r)
		{
			x_m--;
		}
		if(x <= x_m)
		{
			res = min(res,query(node -> l,x_l,x_m,x));
		}
		else
		{
			res = min(res,query(node -> r,x_m + 1,x_r,x));
		}
		return res;
	}

	public:

	LiChaoTree() : root(nullptr) {}
	
	void add_line(const T &a,const T &b)
	{
		Line x(a,b);
		root = add_line(root,x,lower_limit,upper_limit,x.eval(lower_limit),x.eval(upper_limit));
	}

	//[l,r)
	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,lower_limit,upper_limit,x.eval(lower_limit),x.eval(upper_limit));
	}

	T query(const T &x) const
	{
		assert(lower_limit <= x && x <= upper_limit);
		return query(root,lower_limit,upper_limit,x);
	}
};
void Main()
{
	long long a;
	cin >> a;
	LiChaoTree<long long,0,(int)1e9,(long long)1e18> LCT;
	int Q;
	cin >> Q;
	for(;Q--;)
	{
		int t;
		cin >> t;
		if(t == 1)
		{
			int s,g;
			cin >> s >> g;
			LCT.add_segment(s,g + 1,-(s + g),(long long)s * g);
		}
		else
		{
			int x;
			cin >> x;
			long long mn = LCT.query(x);
			if(mn == (long long)1e18)
			{
				cout << "0\n";
			}
			else
			{
				long long ans = -a * ((long long)x * x + mn);
				cout << ans << "\n";
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt = 1;
	/* cin >> tt; */
	while(tt--) Main();
}
0