QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #670740 | #7627. Phony | TLE_Automat | ML | 0ms | 3836kb | C++20 | 7.9kb | 2024-10-23 23:53:19 | 2024-10-23 23:53:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) ((int)((x).size()))
#define lb(x) ((x) & (-(x)))
#define bp(x) __builtin_popcount(x)
#define bpll(x) __builtin_popcountll(x)
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
mt19937 mrnd(std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) {
return mrnd() % (r - l + 1) + l;
}
double rnd01() {
return mrnd() * 1.0 / UINT32_MAX;
}
namespace Fhq_Treap {
const int MAXN = 5e5 + 10;
struct Node {
int lson, rson;
int pri, sz;
ll val;
};
int cnt_id;
Node tree[MAXN << 4];
queue<int> rub;
#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
struct Tree {
int rt = 0;
void clear(int x) {
tree[x].val = tree[x].pri = tree[x].sz = 0;
rub.push(x);
}
void all_clear() {
auto vec = iter_id();
for (auto x : vec) {
clear(x);
}
}
vector<int> iter_id() { // 中序遍历
vector<int> res;
auto dfs = [&](auto &&self, int x) -> void {
if (ls(x)) {
self(self, ls(x));
}
res.push_back(x);
if (rs(x)) {
self(self, rs(x));
}
};
dfs(dfs, rt);
return res;
}
vector<ll> iter_val() {
vector<ll> res;
auto dfs = [&](auto &&self, int x) -> void {
if (ls(x)) {
self(self, ls(x));
}
res.push_back(tree[x].val);
if (rs(x)) {
self(self, rs(x));
}
};
dfs(dfs, rt);
return res;
}
int newp(ll val) {
int cur;
if (!rub.empty()) {
cur = rub.front();
rub.pop();
} else {
cur = ++cnt_id;
}
tree[cur].val = val;
tree[cur].pri = rnd(1, 114514);
tree[cur].sz = 1;
return cur;
}
void push_up(int x) {
tree[x].sz = tree[ls(x)].sz + tree[rs(x)].sz + 1;
}
void split(int x, int &l, int &r, ll val) {
if (!x) {
l = r = 0;
return ;
}
if (tree[x].val <= val) {
l = x;
split(rs(x), rs(l), r, val);
} else {
r = x;
split(ls(x), l, ls(r), val);
}
push_up(x);
}
int merge(int x, int y) {
if (!x || !y) {
return x ^ y;
}
if (tree[x].pri <= tree[y].pri) {
rs(x) = merge(rs(x), y);
return push_up(x), x;
} else {
ls(y) = merge(x, ls(y));
return push_up(y), y;
}
}
void insert(ll val) {
int l_rt, r_rt;
split(rt, l_rt, r_rt, val);
rt = merge(merge(l_rt, newp(val)), r_rt);
}
void del(ll val) {
int l_rt, r_rt, mid_rt;
split(rt, l_rt, r_rt, val);
split(l_rt, l_rt, mid_rt, val - 1);
mid_rt = merge(ls(mid_rt), rs(mid_rt));
rt = merge(merge(l_rt, mid_rt), r_rt);
}
int size() {
return tree[rt].sz;
}
int greater_equal_cnt(ll val) {
int l_rt, r_rt;
split(rt, l_rt, r_rt, val - 1);
int res = tree[r_rt].sz;
rt = merge(l_rt, r_rt);
return res;
}
ll kth_mx(int k) {
int cnt = 0;
int x = rt;
while (true) {
cnt++;
if (cnt > 1000) {
assert(false);
}
if (tree[rs(x)].sz + 1 < k) {
k -= tree[rs(x)].sz + 1;
x = ls(x);
}
else if (tree[rs(x)].sz + 1 > k) {
x = rs(x);
}
else {
return tree[x].val;
}
}
}
};
}
using Fhq_Treap::Tree;
void solve() {
int n, m; ll k;
cin >> n >> m >> k;
vector a(n + 1, 0ll);
const ll D = 1e18;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] += D;
}
sort(a.begin() + 1, a.begin() + n + 1);
map<ll, int> rid;
map<int, ll> pt;
map<int, int> pos;
int mxid = 0, secid = 0;
for (int i = 1; i <= n; i++) {
ll p = a[i] / k;
if (!rid[p]) {
rid[p] = ++mxid;
pt[mxid] = p;
pos[mxid] = i - 1;
}
}
secid = mxid - 1;
vector tr(n + 1, Tree());
for (int i = 1; i <= n; i++) {
ll p = a[i] / k, q = a[i] % k;
tr[rid[p]].insert(q);
}
int mxdc = 0;
auto merge = [&](int x, int y) -> int {
if (tr[x].size() > tr[y].size()) {
swap(x, y);
}
auto vec = tr[x].iter_val();
for (auto cur : vec) {
tr[y].insert(cur);
}
tr[x].all_clear();
return y;
};
while (m--) {
char op;
cin >> op;
if (op == 'C') {
ll t;
cin >> t;
while (true) {
int tot = tr[mxid].size();
if (mxdc + t < tot) {
mxdc += t;
break;
} else if (secid == 0) {
t -= (tot - mxdc);
pt[mxid] = pt[mxid] - 1 - (t / tot);
mxdc = t % tot;
break;
} else {
t -= (tot - mxdc);
mxdc = 0;
if ((pt[mxid] - 1 - pt[secid]) * tot > t) {
pt[mxid] = pt[mxid] - 1 - (t / tot);
mxdc = t % tot;
break;
} else {
t -= (pt[mxid] - 1 - pt[secid]) * tot;
mxid = merge(mxid, secid);
pt[mxid] = pt[secid];
secid--;
}
}
}
} else {
int x;
cin >> x;
int tot = tr[mxid].size();
if (x <= tot - mxdc) {
cout << tr[mxid].kth_mx(mxdc + x) + k * pt[mxid] - D << '\n';
} else {
int sectot = tr[secid].size();
if (x <= tot + sectot) {
x -= tot - mxdc;
ll l = 0, r = 2e18, ans = -1;
while (l <= r) {
ll mid = (l + r) >> 1;
int gecnt = tr[secid].greater_equal_cnt(mid - pt[secid] * k) +
min(tr[mxid].greater_equal_cnt(mid + k - pt[mxid] * k), mxdc);
if (gecnt >= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans - D << '\n';
} else {
x -= (tot + sectot);
cout << a[pos[secid] - x + 1] - D << '\n';
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3836kb
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: 0
Accepted
time: 0ms
memory: 3780kb
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:
294 200 191 0 -2
result:
ok 5 lines
Test #3:
score: -100
Memory Limit Exceeded
input:
100 100 233 5101 8001 6561 6329 6305 7745 4321 811 49 1121 3953 8054 8415 9876 6701 4097 6817 6081 495 5521 2389 2042 4721 8119 7441 7840 8001 5756 5561 129 1 5981 4801 7201 8465 7251 6945 5201 5626 3361 5741 3650 7901 2513 8637 3841 5621 9377 101 3661 5105 4241 5137 7501 5561 3581 4901 561 8721 811...