QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#135881#6400. Game: CelesteClHg2WA 3ms15872kbC++143.2kb2023-08-06 14:33:052023-08-06 14:33:08

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-06 14:33:08]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:15872kb
  • [2023-08-06 14:33:05]
  • 提交

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(); }

Details

Tip: Click on the bar to expand more detailed information

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 '