求助,莫名CE
查看原帖
求助,莫名CE
520777
LaoXu666楼主2023/10/25 13:19
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>

namespace Compare {
	bool Equal(double A, double B, double EPS) {
		return std::abs(A - B) <= EPS;
	}

	bool Greater(double A, double B, double EPS) {
		return (A - B > EPS);
	}

	bool Less(double A, double B, double EPS) {
		return (B - A > EPS);
	}
}

long long F(double X) {
	/*if(X>=0)*/ return std::floor(X);
	/*else return std::ceil(X);*/
}

class LCSegmentTree {
public:
	typedef long long LL;
	static const LL MaxN = 400005;
	const double EPS = 1e-12;
	static const LL LMin = -100005;
	static const LL RMax = 100005;
	const double No_Line = -1e18;
	struct Line {
		double K, Y1;
		LL L, R;
		bool Flag;
	} SegmentTree[MaxN * 4]{};
private:
	static LL LChild(LL Node) { return Node * 2; }

	static LL RChild(LL Node) { return Node * 2 + 1; }

	static double Calc(Line A, LL Position) {
		return A.K * double(Position) + A.Y1;
	}

	static double Cross(Line A, Line B) {
		return (A.Y1 - B.Y1) / (B.K - A.K);
	}

public:
	void Edit(Line LineA, LL Index = 1, LL Left = LMin, LL Right = RMax) {
		if (LineA.L <= Left && Right <= LineA.R) {
			if (!SegmentTree[Index].Flag) {
				SegmentTree[Index] = LineA;
				SegmentTree[Index].Flag = true;
			} else if (Compare::Greater(Calc(LineA, Left), Calc(SegmentTree[Index], Left), EPS) &&
					   Compare::Greater(Calc(LineA, Right), Calc(SegmentTree[Index], Right), EPS))
				SegmentTree[Index] = LineA;
			else if (Compare::Greater(Calc(LineA, Left), Calc(SegmentTree[Index], Left), EPS) ||
					 Compare::Greater(Calc(LineA, Right), Calc(SegmentTree[Index], Right), EPS)) {
				LL Mid = F(double(Left + Right) / 2);
				if (Compare::Greater(Calc(LineA, Mid), Calc(SegmentTree[Index], Mid), EPS)) {
					std::swap(SegmentTree[Index], LineA);
				}
				if (Compare::Greater(double(Mid), double(Cross(LineA, SegmentTree[Index])), EPS))
					Edit(LineA, LChild(Index), Left, Mid);
				else Edit(LineA, RChild(Index), Mid + 1, Right);
			}
		} else {
			LL Mid = F(double(Left + Right) / 2);
			if (LineA.L <= Mid) Edit(LineA, LChild(Index), Left, Mid);
			if (Mid < LineA.R) Edit(LineA, RChild(Index), Mid + 1, Right);
		}
	}

	double Query(LL X, LL Index = 1, LL Left = LMin, LL Right = RMax) {
		if (Left == Right) {
			if (SegmentTree[Index].Flag) {
				//std::cout << Calc(SegmentTree[Index], X) << '\n';
				return Calc(SegmentTree[Index], X);
			}
			return No_Line;
		}
		LL Mid = F(double(Left + Right) / 2);
		double Ans = No_Line;
		if (SegmentTree[Index].Flag) Ans = Calc(SegmentTree[Index], X);
		if (X <= Mid) return std::max(Ans, Query(X, LChild(Index), Left, Mid));
		else return std::max(Ans, Query(X, RChild(Index), Mid + 1, Right));
	}
} P4254_MainTree;

int Q;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> Q;
	
	for (int i = 1; i <= Q; i++) {
		std::string Op;
		std::cin >> Op;
		if (Op == "Query") {
			int Day;
			std::cin >> Day;
			//Day--;
			std::cout << std::floor(P4254_MainTree.Query(Day) / 100) << '\n';
		} else {
			double Start, Plus;
			std::cin >> Start >> Plus;
			Start -= Plus;
			LCSegmentTree::Line This = {Plus, Start, LCSegmentTree::LMin, LCSegmentTree::RMax, true};
			P4254_MainTree.Edit(This);
		}
	}
	return 0;
}

2023/10/25 13:19
加载中...