QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#249757 | #7627. Phony | time_interspace# | WA | 1ms | 6172kb | C++20 | 1.7kb | 2023-11-12 15:07:04 | 2023-11-12 15:07:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define ll long long
#define ls (p<<1)
#define rs (p<<1|1)
ll n, m, k, arr[MAXN];
ll a[MAXN<<2], X[MAXN], xcnt;
unordered_map<ll, int> mp;
void push_up(int p){
a[p] = a[ls] + a[rs];
}
void update(int pos, int l, int r, int p){
if(l == r) return (void) (a[p]++);
int mid = (l+r)>>1;
if(pos <= mid) update(pos, l, mid, ls);
else update(pos, mid+1, r, rs);
push_up(p);
}
int query(int l, int r, int p, int k){
if(l == r) return X[l];
int mid = (l+r)>>1;
if(a[ls] < k) return query(mid+1, r, rs, k-a[ls]);
else return query(l, mid, ls, k);
}
bool cmp(ll x, ll y) {return x > y;}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++) scanf("%lld", &arr[i]), X[i] = arr[i] % k;
sort(arr+1, arr+1+n, cmp);
sort(X+1, X+1+n);
xcnt = unique(X+1, X+1+n) - X - 1;
for(int i=1;i<=xcnt;i++) mp[X[i]] = i;
ll siz = 1, cnt = 0, div = arr[1] / k;
update(mp[arr[1] % k], 1, xcnt, 1);
while(siz < n && arr[siz+1] / k == div) siz++, update(mp[arr[siz] % k], 1, xcnt, 1);
char op[5]; ll x;
for(int i=1;i<=m;i++){
scanf("%s%lld", op, &x);
// printf("cnt = %lld, siz = %lld, div = %lld\n", cnt, siz, div);
if(op[0] == 'C'){
if(cnt + x < siz) {cnt += x; continue;}
x -= siz - cnt; cnt = 0; div--;
while(siz < n && arr[siz+1] / k >= div - x / siz) {
ll tmp = arr[siz+1] / k;
x -= (div - tmp) * siz;
siz++;
update(mp[arr[siz] % k], 1, xcnt, 1);
}
div -= x / siz;
cnt += x % siz;
}else{
if(x <= siz) {
if(cnt + x <= siz) printf("%lld\n", query(1, xcnt, 1, siz+1 - (cnt+x)) + div * k);
else printf("%lld\n", query(1, xcnt, 1, siz+1 - (cnt+x-siz)) + (div-1) * k);
} else printf("%lld\n", arr[x]);
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 6172kb
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: 1ms
memory: 5948kb
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 293 784 471 464
result:
wrong answer 2nd lines differ - expected: '200', found: '293'