QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#728024 | #9574. Strips | ucup-team3931# | WA | 108ms | 18224kb | C++14 | 3.3kb | 2024-11-09 14:23:45 | 2024-11-09 14:24:31 |
Judging History
answer
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1000100;
ll n, m, K, W, a[maxn], b[maxn], lsh[maxn], tot, c[maxn], d[maxn], f[maxn], g[maxn];
namespace SGT {
pii a[maxn << 2];
inline void pushup(int x) {
a[x] = min(a[x << 1], a[x << 1 | 1]);
}
void build(int rt, int l, int r) {
if (l == r) {
a[rt] = mkp(1e18, l);
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
pushup(rt);
}
void update(int rt, int l, int r, int x, ll y) {
if (l == r) {
a[rt].fst = y;
return;
}
int mid = (l + r) >> 1;
(x <= mid) ? update(rt << 1, l, mid, x, y) : update(rt << 1 | 1, mid + 1, r, x, y);
pushup(rt);
}
pii query(int rt, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return a[rt];
}
int mid = (l + r) >> 1;
pii res(1e18, 0);
if (ql <= mid) {
res = min(res, query(rt << 1, l, mid, ql, qr));
}
if (qr > mid) {
res = min(res, query(rt << 1 | 1, mid + 1, r, ql, qr));
}
return res;
}
}
void solve() {
scanf("%lld%lld%lld%lld", &n, &m, &K, &W);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= m; ++i) {
scanf("%lld", &b[i]);
}
tot = 0;
lsh[++tot] = 0;
lsh[++tot] = W;
for (int i = 1; i <= n; ++i) {
if (a[i] + K <= W) {
lsh[++tot] = a[i] + K;
}
if (a[i] + K - 1 <= W) {
lsh[++tot] = a[i] + K - 1;
}
lsh[++tot] = a[i];
if (a[i] - K >= 1) {
lsh[++tot] = a[i] - K;
}
}
for (int i = 1; i <= m; ++i) {
if (b[i] + K <= W) {
lsh[++tot] = b[i] + K;
}
lsh[++tot] = b[i];
lsh[++tot] = b[i] - 1;
if (b[i] - K >= 1) {
lsh[++tot] = b[i] - K;
}
}
sort(lsh + 1, lsh + tot + 1);
tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
for (int i = 1; i <= tot; ++i) {
c[i] = d[i] = 0;
}
for (int i = 1; i <= n; ++i) {
a[i] = lower_bound(lsh + 1, lsh + tot + 1, a[i]) - lsh;
++c[a[i]];
}
for (int i = 1; i <= m; ++i) {
b[i] = lower_bound(lsh + 1, lsh + tot + 1, b[i]) - lsh;
++d[b[i]];
}
for (int i = 1; i <= tot; ++i) {
c[i] += c[i - 1];
d[i] += d[i - 1];
}
SGT::build(1, 1, tot);
f[1] = 0;
SGT::update(1, 1, tot, 1, 0);
ll ans = 1e18, k = -1;
for (int i = 2; i <= tot; ++i) {
if (lsh[i] < K) {
continue;
}
int p = upper_bound(lsh + 1, lsh + tot + 1, lsh[i] - K) - lsh - 1;
if (d[i] > d[p]) {
continue;
}
int l = 1, r = p, q = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (c[p] == c[mid]) {
q = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
pii t = SGT::query(1, 1, tot, q, p);
f[i] = t.fst + 1;
g[i] = t.scd;
SGT::update(1, 1, tot, i, f[i]);
if (c[i] == c[tot]) {
if (f[i] < ans) {
ans = f[i];
k = i;
}
}
}
if (ans > 1e17) {
puts("-1");
return;
}
printf("%lld\n", ans);
while (k > 1) {
printf("%lld ", lsh[k] - K + 1);
k = g[k];
}
putchar('\n');
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 18224kb
input:
4 5 2 3 16 7 11 2 9 14 13 5 3 2 4 11 6 10 2 1 11 2 1 2 6 1 5 3 2 1 2 6 1 5 2
output:
4 14 9 6 2 -1 2 4 1 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 108ms
memory: 18176kb
input:
11000 3 8 2 53 32 3 33 35 19 38 20 1 30 10 6 7 10 1 42 3 14 4 36 28 40 22 17 20 12 41 27 7 1 19 13 9 6 6 13 78 55 76 53 32 54 58 62 45 21 4 7 61 8 7 3 68 9 26 54 31 22 3 38 65 34 16 58 47 52 29 53 5 8 4 33 33 5 30 6 15 27 12 9 28 19 2 13 10 6 1 2 48 8 12 48 1 41 31 40 7 6 7 61 20 19 30 52 49 17 40 3...
output:
2 32 2 7 40 36 28 22 14 4 3 3 64 46 22 8 63 54 36 30 24 20 7 1 3 30 14 3 6 47 41 30 11 7 1 4 47 34 27 14 2 65 42 1 27 1 9 1 62 5 60 47 42 33 24 2 31 3 3 29 20 11 3 33 15 2 3 42 30 25 3 59 17 2 -1 2 65 53 3 65 58 49 3 78 60 43 1 78 4 21 15 11 2 5 48 36 17 7 3 2 44 1 2 25 7 1 ...
result:
wrong answer Participant didn't find a solution but the jury found one. (test case 18)