QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#884211 | #6400. Game: Celeste | xhgua | WA | 249ms | 113628kb | C++17 | 5.0kb | 2025-02-05 22:09:56 | 2025-02-05 22:09:56 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1e6 + 5, BASE = 13331, P = 1e9 + 7;
int T, n, L, R, x[N], a[N], pre[N], pw[N];
bool ban[N];
std::array<int, 2> S[N];
struct PersistentTree {
static constexpr int N = 1e6 + 5, V = 5e7 + 5;
int tot, root[N], ls[V], rs[V], h[V];
void clear() { tot = 0; memset(root, 0, sizeof root); }
void pushUp(int u, int l, int r) {
int mid = (l + r) >> 1;
h[u] = (1ll * h[ls[u]] * pw[r - mid] + h[rs[u]]) % P;
}
void build(int &u, int l, int r) {
u = ++tot;
if (l == r) return h[u] = 0, void();
int mid = (l + r) >> 1;
build(ls[u], l, mid), build(rs[u], mid + 1, r);
pushUp(u, l, r);
}
void modify(int &u, int v, int l, int r, int pos, int val) {
u = ++tot; ls[u] = ls[v], rs[u] = rs[v], h[u] = h[v];
if (l == r) return h[u] += val, void();
int mid = (l + r) >> 1;
if (pos <= mid) modify(ls[u], ls[v], l, mid, pos, val);
if (pos > mid) modify(rs[u], rs[v], mid + 1, r, pos, val);
pushUp(u, l, r);
}
bool compare(int u, int v, int l, int r) {
if (l == r) return h[u] <= h[v];
int mid = (l + r) >> 1;
if (h[rs[u]] == h[rs[v]]) return compare(ls[u], ls[v], l, mid);
return compare(rs[u], rs[v], mid + 1, r);
}
} T1;
struct SegTree {
#define ls(u) (u << 1)
#define rs(u) (u << 1 | 1)
int max[N << 2];
int Max(int lhs, int rhs) {
if (!lhs || !rhs) return lhs + rhs;
return T1.compare(T1.root[lhs], T1.root[rhs], 1, n) ? rhs : lhs;
}
void pushUp(int u) {
max[u] = Max(max[ls(u)], max[rs(u)]);
}
void modify(int u, int l, int r, int pos) {
if (l == r) return max[u] = pos, void();
int mid = (l + r) >> 1;
if (pos <= mid) modify(ls(u), l, mid, pos);
if (pos > mid) modify(rs(u), mid + 1, r, pos);
pushUp(u);
}
int query(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return max[u];
int mid = (l + r) >> 1, ret = 0;
if (ql <= mid) ret = Max(ret, query(ls(u), l, mid, ql, qr));
if (qr > mid) ret = Max(ret, query(rs(u), mid + 1, r, ql, qr));
return ret;
}
} T2;
namespace FastIO {
static constexpr int SIZE = (1 << 20);
char bufIn[SIZE], bufOut[SIZE], *p1, *p2, *pOut = bufOut;
#define gc() (p1 == p2 && (p2 = (p1 = bufIn) + fread(bufIn, 1, 1 << 20, stdin)), p1 == p2 ? EOF : *p1++)
#define pc(c) (pOut - bufOut == SIZE && (fwrite(bufOut, 1, 1 << 20, stdout), pOut = bufOut), *pOut++ = c)
template <typename T>
inline void read(T &x) {
x = 0; bool f = 0; char ch = gc();
while(!isdigit(ch)) f |= (ch == '-'), ch = gc();
while( isdigit(ch)) x = x * 10 + (ch - '0'), ch = gc();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &...args){ read(x); read(args...); }
template <typename T = int>
inline T read() {
T x = 0; bool f = 0; char ch = gc();
while(!isdigit(ch)) f |= (ch == '-'), ch = gc();
while( isdigit(ch)) x = x * 10 + (ch - '0'), ch = gc();
return f ? -x : x;
}
template <typename T>
inline void write(T x) {
if (x < 0) x = -x, pc('-');
static T stk[40]; int tp = 0;
do stk[tp++] = x % 10, x /= 10; while(x);
while(tp) pc(stk[--tp] + '0');
}
template <typename T, typename... Args>
inline void write(T x, Args ...args){ write(x); pc(' '); write(args...); }
template <typename T> inline void writeln(T x) { write(x); pc('\n'); }
template <typename T> inline void writesp(T x) { write(x); pc(' '); }
inline void flush() { fwrite(bufOut, 1, pOut - bufOut, stdout); }
};
using namespace FastIO;
void solve() {
n = read(), L = read(), R = read();
for (int i = 1; i <= n; i++) x[i] = read(), ban[i] = pre[i] = 0;
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= n; i++) {
S[i][0] = std::lower_bound(x + 1, x + 1 + n, x[i] - R) - x;
S[i][1] = std::upper_bound(x + 1, x + 1 + n, x[i] - L) - x - 1;
}
T1.build(T1.root[0], 1, n), T1.modify(T1.root[1], T1.root[0], 1, n, a[1], 1);
for (int i = 1; i <= (n << 2); i++) T2.max[i] = 0;
T2.modify(1, 1, n, 1);
std::deque<int> q; int curR = 0;
for (int i = 2; i <= n; i++) {
auto [l, r] = S[i];
if (l > r) { ban[i] = 1; continue; }
while (!q.empty() && q.front() < l) q.pop_front();
while (curR < r) {
if (ban[curR + 1]) {
++curR;
continue;
}
while (!q.empty() && T2.Max(curR + 1, q.back()) == curR + 1) q.pop_back();
q.push_back(++curR);
}
if (!q.empty()) pre[i] = q.front();
if (!pre[i]) { ban[i] = 1; continue; }
T1.modify(T1.root[i], T1.root[pre[i]], 1, n, a[i], 1);
T2.modify(1, 1, n, i);
}
if (ban[n]) return writeln(-1), void();
int cur = n; std::vector<int> ans;
while (cur) {
ans.push_back(a[cur]);
cur = pre[cur];
}
std::sort(ans.begin(), ans.end(), std::greater<int>());
writeln(ans.size());
for (auto u : ans) writesp(u);
pc('\n');
}
int main() {
pw[0] = 1;
for (int i = 1; i < N; i++) pw[i] = 1ll * pw[i - 1] * BASE % P;
T = read();
while (T--) solve();
return flush(), 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 24020kb
input:
2 5 2 3 1 2 3 4 5 5 2 3 1 4 3 1 2 1 4 7 3 3 3
output:
3 5 4 3 -1
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 249ms
memory: 113628kb
input:
10000 57 8 11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 11 16 7 7 10 13 9 14 10 1 12 4 8 13 3 20 16 7 16 19 20 8 19 7 16 6 17 13 7 19 17 11 12 17 6 3 7 8 14 2 4 15 5 18 16 7 20 9 1...
output:
7 20 20 19 14 12 11 3 -1 6 6 5 3 2 1 1 -1 185 20 20 20 20 20 20 20 20 19 19 19 19 19 19 19 19 19 19 19 19 18 18 18 18 18 17 17 17 17 17 17 17 17 16 16 16 16 16 16 16 16 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 14 14 14 14 14 14 14 13 13 13 13 13 13 13 13 13 12 12 12 12 12 12 12 ...
result:
wrong answer 85th lines differ - expected: '-1', found: '2'