QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#481638#8831. Chemistry Classucup-team4361RE 0ms3868kbC++202.8kb2024-07-17 11:57:302024-07-17 11:57:30

Judging History

你现在查看的是最新测评结果

  • [2024-07-17 11:57:30]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3868kb
  • [2024-07-17 11:57:30]
  • 提交

answer

#include <bits/stdc++.h>

using std::vector, std::array, std::string;
using std::set, std::map, std::multiset;
using std::min, std::max, std::swap;
using std::pair, std::tuple;
using std::tie;
using std::abs, std::sin, std::cos, std::tan, std::asin, std::acos, std::atan2;
using std::cin, std::cout;

template <class T> using Vec = vector<T>;
template <class T> using Opt = std::optional<T>;

using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;

std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());

template <class T, class F> struct QueueAggregation {
	const F f; /// start-hash
	const T e;
	Vec<T> as, bs, ae, be;
	T vs, ve;
	QueueAggregation(F f_, T e_) : f(f_), e(e_), vs(e), ve(e) {} /// end-hash

	void push_s(const T& x) { /// start-hash
		as.push_back(x), bs.push_back(vs = f(x, vs));
	}
	void push_e(const T& x) {
		ae.push_back(x), be.push_back(ve = f(ve, x));
	}
	void reduce() {
		while (!ae.empty()) {
			push_s(ae.back()), ae.pop_back();
		}
		be.clear();
		ve = e;
	} /// end-hash

	bool empty() const { /// start-hash
		return as.empty() && ae.empty();
	}
	int size() const {
		return int(as.size() + ae.size());
	} /// end-hash

	void push(const T& x) { /// start-hash
		if (as.empty()) {
			push_s(x), reduce();
		} else {
			push_e(x);
		}
	}
	void pop() {
		assert(!empty());
		if (as.empty()) reduce();
		as.pop_back(), bs.pop_back();
		vs = (bs.empty() ? e : bs.back());
	}
	T prod() const {
		return f(vs, ve);
	} /// end-hash
};

int solve(int N, i64 A, i64 B, const Vec<i64>& S) {
	for (int i = 0; i < N; i++) {
		if (S[2*i+1] - S[2*i] > A) {
			return -1;
		}
	}

	int cur_dp = 0;
	int pref_cnt = 0;
	int first_pairable = 0;

	auto qa = QueueAggregation([](int a, int b) -> int {
		return max(a, b);
	}, int(-1e8));
	qa.push(cur_dp - 0);

	for (int i = 0; i < N; i++) {
		int nxt_dp = cur_dp + int(S[2*i+1] - S[2*i] <= B);

		if (i > 0 && S[2*i] - S[2*i-1] <= B) {
			pref_cnt++;
		}
		// unsafe but whatever
		while (S[2*i+1] - S[2*first_pairable] > A) {
			qa.pop();
		}
		// nxt_dp = max(nxt_dp, query(first_pairable, i+1) + pref_cnt);
		nxt_dp = max(nxt_dp, qa.prod() + pref_cnt);
		// dp[i+1] is now computed correctly

		cur_dp = std::move(nxt_dp);
		if (i+1 < N) {
			// must subtract away the contribution of (2*i+1, 2*i+2)
			int sub = pref_cnt + int(S[2*i+2] - S[2*i+1] <= B);
			qa.push(cur_dp - sub);
		}
	}
	return cur_dp;
}

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

	int T;
	cin >> T;
	while (T--) {
		int N;
		i64 A, B;
		cin >> N >> A >> B;
		auto S = Vec<i64>(2*N);
		for (auto& s : S) {
			cin >> s;
		}
		std::ranges::sort(S);

		cout << solve(N, A, B, S) << '\n';
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3868kb

input:

4
1 2 1
42 69
2 3 1
1 2 3 4
2 5 1
6 1 3 4
5 19 1
1 7 8 9 10 11 12 13 14 20

output:

-1
2
1
4

result:

ok 4 number(s): "-1 2 1 4"

Test #2:

score: -100
Runtime Error

input:

1
199996 67013419502794 1
403716252634677166 895717933735068492 410002430455111886 844431179242134559 322988383133810700 133475121268220299 481706326769800263 606871141911985391 195911124687409946 959578180866483093 930547702157856949 877914383714875160 994158366044742636 890855755285236186 69498488...

output:


result: