QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#249757#7627. Phonytime_interspace#WA 1ms6172kbC++201.7kb2023-11-12 15:07:042023-11-12 15:07:04

Judging History

你现在查看的是最新测评结果

  • [2023-11-12 15:07:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6172kb
  • [2023-11-12 15:07:04]
  • 提交

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'