QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#135881 | #6400. Game: Celeste | ClHg2 | WA | 3ms | 15872kb | C++14 | 3.2kb | 2023-08-06 14:33:05 | 2023-08-06 14:33:08 |
Judging History
answer
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <random>
#include <vector>
namespace {
using std::cin;
using std::cout;
using std::int64_t;
const int kN = 1.0e6, kMaxN = kN + 5, kMaxM = kMaxN << 5;
int n, l, r;
int a[kMaxN], b[kMaxN], pre[kMaxN];
bool vis[kMaxN];
std::deque<int> q;
namespace random {
std::mt19937 rng(std::chrono::system_clock().now().time_since_epoch().count());
inline int RandInt(int l, int r) {
return std::uniform_int_distribution<>(l, r)(rng);
}
} // namespace random
namespace hash {
const int kP = 1.0e9 + 7, kB = random::RandInt(kN + 1, kP - 1);
int pow_b[kMaxN];
void Init(int n) {
pow_b[0] = 1;
for (int i = 1; i <= n; ++i) pow_b[i] = int64_t{pow_b[i - 1]} * kB % kP;
}
} // namespace hash
namespace persistent_segment_tree {
int tot;
int rt[kMaxN], lc[kMaxM], rc[kMaxM], cnt[kMaxM], hash[kMaxM];
void Clear() {
std::fill_n(rt, n + 1, 0);
std::fill_n(lc + 1, tot, 0), std::fill_n(rc + 1, tot, 0);
std::fill_n(cnt + 1, tot, 0), std::fill_n(hash + 1, tot, 0);
tot = 0;
}
int Insert(int p, int l, int r, int x) {
int q = ++tot;
cnt[q] = cnt[p] + 1, hash[q] = hash[p] + hash::pow_b[x];
if (hash[q] >= hash::kP) hash[q] -= hash::kP;
if (l == r) return q;
int mid = (l + r) >> 1;
if (x <= mid) {
lc[q] = Insert(lc[p], l, mid, x), rc[q] = rc[p];
} else {
lc[q] = lc[p], rc[q] = Insert(rc[p], mid + 1, r, x);
}
return q;
}
int Insert(int p, int x) { return Insert(p, 1, n, x); }
int Cmp(int p, int q, int l, int r) {
if (hash[p] == hash[q]) return 0;
if (l == r) return cnt[p] < cnt[q] ? -1 : 1;
int mid = (l + r) >> 1, ans = Cmp(rc[p], rc[q], mid + 1, r);
if (ans == 0) ans = Cmp(lc[p], lc[q], l, mid);
return ans;
}
int Cmp(int p, int q) { return Cmp(p, q, 1, n); }
} // namespace persistent_segment_tree
using persistent_segment_tree::rt;
void Solve() {
cin >> n >> l >> r;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i];
persistent_segment_tree::Clear(), q.clear();
rt[1] = persistent_segment_tree::Insert(rt[0], b[1]);
std::fill_n(vis + 1, n, false), vis[1] = true;
int p = 1;
for (int i = 2; i <= n; ++i) {
while (a[p] <= a[i] - l) {
if (vis[p]) {
while (!q.empty() &&
persistent_segment_tree::Cmp(rt[q.back()], rt[p]) <= 0) {
q.pop_back();
}
q.emplace_back(p);
}
++p;
}
while (!q.empty() && a[q.front()] < a[i] - r) q.pop_front();
if (!q.empty()) {
vis[i] = true, pre[i] = q.front();
rt[i] = persistent_segment_tree::Insert(rt[q.front()], b[i]);
}
}
if (!vis[n]) {
cout << "-1\n";
} else {
std::vector<int> c;
for (int i = n; i; i = pre[i]) c.emplace_back(b[i]);
std::sort(c.begin(), c.end(), std::greater<>());
for (int x : c) cout << x << " ";
cout << "\n";
}
}
int Main() {
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
hash::Init(kN);
int t;
cin >> t;
while (t--) Solve();
return 0;
}
} // namespace
int main() { return Main(); }
詳細信息
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 15872kb
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 '