QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#220588#7627. PhonyHeltion#WA 0ms3584kbC++203.3kb2023-10-20 16:05:032023-10-20 16:05:03

Judging History

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

  • [2023-10-20 16:05:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3584kb
  • [2023-10-20 16:05:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using u64 = int64_t;
using f64 = double_t;
constexpr i64 mod = 998244353;
struct Node {
  static constexpr bool persistent = true;
  static mt19937_64 mt;
  Node *l, *r;
  u64 priority;
  int size;
  i64 v;
  Node(const Node &other) { memcpy(this, &other, sizeof(Node)); }
  Node(int v) : v(v), priority(mt()), size(1) { l = r = nullptr; }
  Node *update(Node *l, Node *r) {
    Node *p = persistent ? new Node(*this) : this;
    p->l = l;
    p->r = r;
    p->size = (l ? l->size : 0) + 1 + (r ? r->size : 0);
    return p;
  }
};
mt19937_64 Node::mt;
pair<Node *, Node *> split_by_v(Node *p, i64 v) {
  if (not p) { return {}; }
  if (p->v < v) {
    auto [l, r] = split_by_v(p->r, v);
    return {p->update(p->l, l), r};
  }
  auto [l, r] = split_by_v(p->l, v);
  return {l, p->update(r, p->r)};
}
pair<Node *, Node *> split_by_size(Node *p, int size) {
  if (not p) { return {}; }
  int l_size = p->l ? p->l->size : 0;
  if (l_size < size) {
    auto [l, r] = split_by_size(p->r, size - l_size - 1);
    return {p->update(p->l, l), r};
  }
  auto [l, r] = split_by_size(p->l, size);
  return {l, p->update(r, p->r)};
}
Node *merge(Node *l, Node *r) {
  if (not l or not r) { return l ?: r; }
  if (l->priority < r->priority) { return r->update(merge(l, r->l), r->r); }
  return l->update(l->l, merge(l->r, r));
}
i64 div_f(i64 x, i64 k) { return x / k - (x < 0 and x % k); }

Node *insert(Node *p, i64 v) {
  auto [l, r] = split_by_v(p, v);
  return merge(merge(l, new Node(v)), r);
}
int kth(Node *p, int k) {
  int l_size = p->l ? p->l->size : 0;
  if (l_size == k) { return p->v; }
  if (k < l_size) { return kth(p->l, k); }
  return kth(p->r, k - 1 - l_size);
}
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  i64 k;
  cin >> n >> m >> k;
  vector<i64> a(n);
  for (i64 &ai : a) { cin >> ai; }
  ranges::sort(a);
  Node *top = nullptr;
  i64 d = div_f(a.back(), k), vir = 0;
  int st = n - 1;
  auto flush = [&]() {
    while (st >= 0) {
      i64 di = div_f(a[st], k);
      if (di == d) {
        top = insert(top, a[st] - d * k);
      } else if (a[st] >= kth(top, top->size - vir - 1)) {
        vir += 1;
        top = insert(top, a[st] - d * k + k);
      } else {
        break;
      }
      st -= 1;
    }
  };
  flush();
  for (int i = 0; i < m; i += 1) {
    char c;
    cin >> c;
    if (c == 'C') {
      i64 t;
      cin >> t;
      while (t > 0) {
        if (top->size - vir > t) {
          vir += t;
          break;
        }
        if (vir > 0) {
          t -= top->size - vir;
          vir = 0;
          d -= 1;
          flush();
        } else if (st == -1) {
          d -= t / top->size;
          t %= top->size;
        } else {
          i64 x = min(d - div_f(a[st], k) - 1, t / top->size);
          d -= x;
          t -= x * top->size;
          flush();
        }
      }
    } else {
      int x;
      cin >> x;
      if (x > top->size) {
        cout << a[n - x] << "\n";
        continue;
      } else if (x <= top->size - vir) {
        cout << kth(top, top->size - vir - x) + d * k << "\n";
      } else {
        cout << kth(top, top->size - x + (top->size - vir)) + (d - 1) * k
             << "\n";
      }
    }
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3

output:

3
4
-1

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3532kb

input:

5 8 8
294 928 293 392 719
A 4
C 200
A 5
C 10
A 2
C 120
A 1
A 3

output:

392
-26
584
-227
191

result:

wrong answer 1st lines differ - expected: '294', found: '392'