QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#249183 | #7627. Phony | ucup-team1516# | WA | 0ms | 3760kb | C++17 | 6.5kb | 2023-11-12 01:51:17 | 2023-11-12 01:51:18 |
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;
// n = myRand(1000)+1, q = myRand(10000)+1;
ll K;
// K = myRand(1000)+1;
cin >> K;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
// a[i] = myRand(100);
}
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 {
// cntは0になっているはず
// 追加した直後なので
ll dif = z[pos]-z[md[sz]];
if (dif < 0) dif += K;
nx = bitsum(pos, md[sz]);
ll uo = mx-dif;
nx += (__int128)(uo-a[sz]-K)/K*(__int128)sz;
}
};
calNext();
auto debug = [&]() -> void {
cout << "bbb" << endl;
for (int i = 0; i < m; ++i) {
cout << bbb[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;
// if (myRand(2) == 0) {
// c = 'A';
// }
// else {
// c = 'C';
// }
// ll uouo = myRand(n)+1;
ll uouo; cin >> uouo;
if (c == 'A') {
int x = uouo;
if (sz < x) {
cout << a[x-1] << "\n";
}
else {
ll dif = findKth(pos, x, cnt);
cout << mx-dif << "\n";
}
}
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;
pos = md[sz];
add(md[sz]);
update();
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();
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3528kb
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: 3600kb
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: 3760kb
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 2945 7734 7556 5291 5001 2042 4721 4721 6881 4097 7302 7324 7149 7208 811 6945 2561 6945 6442 6503 3581 5291 1485 6302 6135 2042 6053 6115 6159 4721 6013 4029 4097 4901 5789 4721 5649 2042 5649 5521 5692 5482 3581 5393 115 2042 5328 2042 5328 1485 5386 -16686
result:
wrong answer 4th lines differ - expected: '8200', found: '8230'