QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310790 | #6400. Game: Celeste | memset0 | WA | 2ms | 7612kb | C++20 | 2.1kb | 2024-01-21 17:59:58 | 2024-01-21 17:59:59 |
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 {
for (int i = 0; i < f[n].v.size(); i++)
cout << f[n].v[i] << " \n"[i + 1 == f[n].v.size()];
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 7612kb
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:
5 4 3 -1
result:
wrong answer 1st lines differ - expected: '3', found: '5 4 3'