QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#250302 | #7627. Phony | ucup-team1516 | WA | 0ms | 3620kb | C++17 | 6.6kb | 2023-11-13 02:09:36 | 2023-11-13 02:09:36 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
inline double time() {
return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}
// 0-indexed
template<typename T>
struct BIT{
int n;
vector<T> bit;
BIT (int n = 0) : n(n),bit(n+1) {}
// [0, i)
T sum (int i) {
T res = 0;
for (; i > 0; i -= (i&-i)) {
res += bit[i];
}
return res;
}
// [l, r)
T sum (int l, int r) {
return sum(r) - sum(l);
}
void add (int i, T a) {
i++;
for (; i <= n; i += (i&-i)) {
bit[i] += a;
}
}
int lower_bound (T k) { // k <= sum(res)
if (k <= 0) return 0;
int res = 0, i = 1;
while ((i << 1) <= n) i <<= 1;
for (; i ; i >>= 1) {
if (res+i <= n and bit[res+i] < k) {
k -= bit[res += i];
}
}
return res;
}
};
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n,q; cin >> n >> q;
ll K; cin >> K;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.rbegin(), a.rend());
vector<ll> z(n);
for (int i = 0; i < n; ++i) {
z[i] = a[i]%K;
}
sort(z.begin(), z.end());
z.erase(unique(z.begin(), z.end()), z.end());
int m = z.size();
int sz = 0;
BIT<int> bit(m);
vector<int> bbb(m);
auto add = [&](int i) -> void {
sz += 1;
bit.add(i, 1);
bbb[i] += 1;
};
vector<int> md(n);
for (int i = 0; i < n; ++i) {
md[i] = lower_bound(z.begin(), z.end(), a[i]%K) - z.begin();
if (a[0]-a[i] < K) {
add(md[i]);
}
}
// bit[i]+bit[i-1]+bit[i-2]+...が初めてkを超える位置を求めたい
// ただしiは既にcnt個使われているものとする
// 最大値との差分を返すように設計したいねえ
auto findKth = [&](int i, int k, int cnt) -> ll {
if (bbb[i]-cnt >= k) return 0;
if (sz-cnt < k) return K;
int f = k-(bbb[i]-cnt);
if (bit.sum(i) >= f) {
int l = 0, r = i;
while (r-l > 1) {
int mid = (l+r)/2;
if (bit.sum(mid, i) >= f) {
l = mid;
}
else {
r = mid;
}
}
return z[i]-z[l];
}
else {
f -= bit.sum(i);
int l = 0, r = m;
while (r-l > 1) {
int mid = (l+r)/2;
if (sz - bit.sum(mid) >= f) {
l = mid;
}
else {
r = mid;
}
}
return z[i]+K-z[l];
}
};
int pos = md[0];
int cnt = 0;
ll mx = a[0];
__int128 nx = 0;
auto bitsum = [&](int s, int t) -> int {
if (t <= s) {
return bit.sum(t, s+1);
}
else {
return sz-bit.sum(s+1,t);
}
};
auto calNext = [&]() -> void {
if (sz >= n) {
return;
}
else {
ll dif = z[pos]-z[md[sz]];
if (dif < 0) dif += K;
nx = bitsum(pos, md[sz])-cnt;
ll uo = mx-dif;
nx += (__int128)(uo-a[sz]-K)/K*(__int128)sz;
}
};
calNext();
vector<pair<char,ll>> query;
auto debug = [&]() -> void {
cout << "debug" << endl;
for (int i = 0; i < query.size(); ++i) {
cout << query[i].first << " " << query[i].second << endl;
}
cout << "A" << endl;
for (int i = 0; i < 18; ++i) {
cout << a[i] << " ";
}
cout << endl;
cout << "pos = " << pos << endl;
cout << "cnt = " << cnt << endl;
cout << "mx = " << mx << endl;
cout << "nx = " << (ll)nx << endl;
};
while (q--) {
char c; cin >> c;
ll uouo; cin >> uouo;
query.push_back({c, uouo});
if (c == 'A') {
int x = uouo;
ll res;
if (sz < x) {
res = a[x-1];
}
else {
ll dif = findKth(pos, x, cnt);
res = mx-dif;
}
cout << res << "\n";
if (res == 8230) {
cout << x << " " << sz << endl;
debug();
return 0;
}
}
else {
auto update = [&]() -> void {
if (pos) {
mx -= z[pos]-z[pos-1];
pos -= 1;
cnt = 0;
}
else {
mx -= z[0]-z[m-1]+K;
pos = m-1;
cnt = 0;
}
};
ll t = uouo;
while (sz < n and t >= nx) {
t -= nx;
mx = a[sz]+K;
int j = md[sz];
pos = j;
add(j);
cnt = bbb[j];
calNext();
}
ll u = t/sz;
mx -= u*K;
t -= u*sz;
if (bbb[pos]-cnt >= t) {
cnt += t;
}
else {
t -= (bbb[pos]-cnt);
update();
// debug();
if (bit.sum(pos+1) <= t) {
t -= bit.sum(pos+1);
mx -= z[pos]-z.back()+K;
pos = m-1;
cnt = 0;
}
// (r,pos]は全消し可能
int l = -1, r = pos;
while (r-l > 1) {
int mid = (l+r)/2;
if (bit.sum(mid+1,pos+1) <= t) {
r = mid;
}
else {
l = mid;
}
}
t -= bit.sum(r+1,pos+1);
mx -= z[pos]-z[r];
pos = r;
cnt = 0;
assert(bbb[pos] >= t);
cnt = t;
}
// debug();
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
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: 3620kb
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
Wrong Answer
time: 0ms
memory: 3560kb
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...
output:
6881 9161 4721 8230 1 18 debug C 11 A 31 A 1 A 61 C 1 C 39 A 1 A 9876 9861 9421 9377 9161 9153 8977 8721 8637 8465 8433 8415 8119 8113 8081 8054 8001 8001 pos = 32 cnt = 0 mx = 8230 nx = 8
result:
wrong answer 4th lines differ - expected: '8200', found: '8230'