QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#310792 | #6400. Game: Celeste | memset0 | RE | 2ms | 7692kb | C++20 | 2.1kb | 2024-01-21 18:00:40 | 2024-01-21 18:00:42 |
Judging History
answer
#include <bits/stdc++.h>
#ifndef popteam
#define endl '\n'
#endif
#define all(x) begin(x), end(x)
using namespace std;
const int N = 1e6 + 9;
int T, n, xl, xr, x[N], a[N];
struct sequence {
vector<int> v;
bool empty() { return v.empty(); }
bool operator>(const sequence &rhs) const {
for (size_t i = 0; i < v.size() && i < rhs.v.size(); i++)
if (v[i] != rhs.v[i]) {
return v[i] > rhs.v[i];
}
return v.size() > rhs.v.size();
}
sequence insert(int x) {
sequence it = *this;
it.v.push_back(x);
sort(all(it.v), [&](int x, int y) { return x > y; });
return it;
}
} f[N];
deque<pair<int, sequence>> q;
int main() {
#ifdef popteam
freopen("G.in", "r", stdin);
#endif
cin.tie(0)->sync_with_stdio(0);
cin >> T;
while (T--) {
cin >> n >> xl >> xr;
for (int i = 1; i <= n; i++)
cin >> x[i];
for (int i = 1; i <= n; i++)
cin >> a[i];
q.clear();
int j = 1;
for (int i = 1; i <= n; i++) {
if (i == 1) {
f[i] = {{a[1]}};
} else {
f[i] = {{}};
}
while (j < i && x[j] + xl <= x[i] && x[i] <= x[j] + xr) {
while (q.size() && f[j] > q.back().second) {
q.pop_back();
}
q.push_back(make_pair(j, f[j]));
j++;
}
// fprintf(stderr, "i=%d\n", i);
// for (auto x : q)
// cerr << x.first << " ";
// cerr << endl;
while (q.size() && x[q.front().first] + xl > x[i] || x[q.front().first] + xr < x[i]) {
q.pop_front();
}
if (q.size()) {
f[i] = q.front().second.insert(a[i]);
}
}
if (f[n].empty()) {
cout << -1 << endl;
} else {
cout << f[n].v.size() << endl;
for (int i = 0; i < f[n].v.size(); i++)
cout << f[n].v[i] << " \n"[i + 1 == f[n].v.size()];
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 7692kb
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
Runtime Error
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...