QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#220588 | #7627. Phony | Heltion# | WA | 0ms | 3584kb | C++20 | 3.3kb | 2023-10-20 16:05:03 | 2023-10-20 16:05:03 |
Judging History
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'