QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#457750 | #8831. Chemistry Class | ucup-team987# | WA | 89ms | 13720kb | C++23 | 7.5kb | 2024-06-29 13:53:55 | 2024-06-29 13:53:56 |
Judging History
answer
#if __INCLUDE_LEVEL__ == 0
#include __BASE_FILE__
namespace {
Int op(Int x, Int y) { return std::max(x, y); }
Int e() { return -inf(); }
void solve() {
Int n, A, B;
scan(n, A, B);
Vec<Int> a(2 * n);
scan(a);
ranges::sort(a);
Int base = 0;
for (i : rep(n)) {
if (a[2 * i] + A < a[2 * i + 1]) {
print(-1);
return;
}
base += a[2 * i + 1] <= a[2 * i] + B;
}
Vec<Int> suff(n + 1);
for (i : rev(rep(n))) {
suff[i] = suff[i + 1];
if (i) {
suff[i] += a[2 * i] <= a[2 * i - 1] + B;
suff[i] -= a[2 * i + 1] <= a[2 * i] + B;
}
}
atcoder::segtree<Int, op, e> seg(n);
Vec<Int> f(n + 1);
for (l : rev(rep(n))) {
f[l] = f[l + 1];
Int cur = 0;
cur -= a[2 * l + 1] <= a[2 * l] + B;
Int ok = l;
Int ng = n;
while (ok + 1 < ng) {
Int mid = std::midpoint(ok, ng);
(a[2 * mid] + A < a[2 * mid + 1] ? ng : ok) = mid;
}
seg.set(l, f[l + 1] - suff[l + 1]);
chmax(f[l], cur + suff[l + 1] + seg.prod(l + 1, ng));
}
print(base + f[0]);
}
} // namespace
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::setprecision(std::numeric_limits<Float>::max_digits10);
Int t;
scan(t);
while (t--) {
solve();
}
}
#else // __INCLUDE_LEVEL__
#include <bits/stdc++.h>
namespace atcoder {
namespace internal {
using std::bit_ceil;
int countr_zero(unsigned int n) { return __builtin_ctz(n); }
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
template <class S, auto op, auto e>
struct segtree {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
public:
segtree() : segtree(0) {}
explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
size = (int)internal::bit_ceil((unsigned int)(_n));
log = internal::countr_zero((unsigned int)size);
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() const { return d[1]; }
template <bool (*f)(S)>
int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F>
int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)>
int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F>
int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
using Int = int64_t;
using Float = double;
using Str = std::string;
template <class T1, class T2>
using Pair = std::pair<T1, T2>;
template <class... Ts>
using Tuple = std::tuple<Ts...>;
template <class T, size_t N>
using Arr = std::array<T, N>;
template <class T>
using Vec = std::vector<T>;
template <class T>
using Set = std::set<T>;
template <class T>
using Multiset = std::multiset<T>;
template <class K, class T>
using Map = std::map<K, T>;
template <class T>
using MinHeap = std::priority_queue<T, Vec<T>, std::greater<T>>;
template <class T>
using MaxHeap = std::priority_queue<T>;
namespace ranges = std::ranges;
namespace views = std::views;
inline constexpr auto len = ranges::ssize;
inline constexpr auto rev = views::reverse;
constexpr auto rep(Int l, Int r) { return views::iota(std::min(l, r), r); }
constexpr auto rep(Int n) { return rep(0, n); }
constexpr auto rep1(Int l, Int r) { return rep(l, r + 1); }
constexpr auto rep1(Int n) { return rep(1, n + 1); }
template <class T, class U = T>
bool chmin(T& x, U&& y) {
return y < x && (x = std::forward<U>(y), true);
}
template <class T, class U = T>
bool chmax(T& x, U&& y) {
return x < y && (x = std::forward<U>(y), true);
}
template <std::signed_integral T = Int>
T inf() {
T ret;
std::memset(&ret, 0x3f, sizeof(ret));
return ret;
}
template <std::floating_point T>
T inf() {
return std::numeric_limits<T>::infinity();
}
template <class T>
concept Range = ranges::range<T> && !std::convertible_to<T, std::string_view>;
template <class T>
concept TupleLike = std::__is_tuple_like<T>::value && !Range<T>;
namespace std {
istream& operator>>(istream& is, Range auto&& r) {
for (auto&& e : r) {
is >> e;
}
return is;
}
istream& operator>>(istream& is, TupleLike auto&& t) {
return apply([&](auto&... xs) -> istream& { return (is >> ... >> xs); }, t);
}
ostream& operator<<(ostream& os, Range auto&& r) {
for (string_view sep = ""; auto&& e : r) {
os << exchange(sep, " ") << e;
}
return os;
}
ostream& operator<<(ostream& os, TupleLike auto&& t) {
const auto f = [&](auto&... xs) -> ostream& {
[[maybe_unused]] string_view sep = "";
((os << exchange(sep, " ") << xs), ...);
return os;
};
return apply(f, t);
}
} // namespace std
#define DEF_INC_OR_DEC(op) \
auto& operator op(Range auto&& r) { \
for (auto&& e : r) { \
op e; \
} \
return r; \
} \
auto& operator op(TupleLike auto&& t) { \
std::apply([](auto&... xs) { (op xs, ...); }, t); \
return t; \
}
DEF_INC_OR_DEC(++)
DEF_INC_OR_DEC(--)
#undef DEF_INC_OR_DEC
void scan(auto&&... xs) { std::cin >> std::tie(xs...); }
void print(auto&&... xs) { std::cout << std::tie(xs...) << '\n'; }
template <class F>
class fix {
public:
explicit fix(F f) : f_(std::move(f)) {}
decltype(auto) operator()(auto&&... xs) const {
return f_(std::ref(*this), std::forward<decltype(xs)>(xs)...);
}
private:
F f_;
};
#define for(...) for ([[maybe_unused]] auto&& __VA_ARGS__)
#endif // __INCLUDE_LEVEL__
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3872kb
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: 0
Accepted
time: 89ms
memory: 13632kb
input:
1 199996 67013419502794 1 403716252634677166 895717933735068492 410002430455111886 844431179242134559 322988383133810700 133475121268220299 481706326769800263 606871141911985391 195911124687409946 959578180866483093 930547702157856949 877914383714875160 994158366044742636 890855755285236186 69498488...
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 83ms
memory: 13720kb
input:
1 199998 38987266278826 1 974183459404323858 517476981059568123 730207399881008603 532509909948600146 89227878552241675 16653300445469756 791674368913652595 92177901403222015 980536748304824579 581564387828767376 471919726893404451 759601909683722004 632340812998214017 818440789777778368 18845836031...
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 84ms
memory: 13516kb
input:
1 199996 54170919220045 1 968843690955781467 596307347951820347 406785475849275444 383666938223357986 725160735782817082 132577412512120631 891899794864087098 779434145671998619 932681297277907326 208765550447928461 385078857912267975 669360937040314510 917331948890514855 505938744714587815 47145437...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: -100
Wrong Answer
time: 85ms
memory: 13540kb
input:
1 199998 35667463938291 8255384928693 770468016026697053 519790816750772730 110085058423772871 85144239858008037 782003096084947976 938498644167289660 693768718229582367 242186248813489674 155335549252315364 428982852761422230 890445026369869037 86401573937739054 9122788624365829 63351367715811463 1...
output:
196259
result:
wrong answer 1st numbers differ - expected: '193326', found: '196259'