QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#481638 | #8831. Chemistry Class | ucup-team4361 | RE | 0ms | 3868kb | C++20 | 2.8kb | 2024-07-17 11:57:30 | 2024-07-17 11:57:30 |
Judging History
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...