QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#757877 | #7627. Phony | -Ofast | TL | 0ms | 0kb | C++11 | 2.0kb | 2024-11-17 14:15:04 | 2024-11-17 14:15:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,k;
long long a[N],b[N],c[N],id[N],t,x,sum,cnt;
__int128 suf[N];
signed tree[N*25],l[N*25],r[N*25],root[N];
bool cmp(int x,int y){
if(c[x]!=c[y])return c[x]>c[y];
return x>y;
}
void update(signed &rt,int left,int right,int x){
++cnt;l[cnt]=l[rt];r[cnt]=r[rt];
tree[cnt]=tree[rt]+1;rt=cnt;
if(left==right)return;
int mid=(left+right)>>1;
if(x<=mid)update(l[rt],left,mid,x);
else update(r[rt],mid+1,right,x);
}
int query(int rt,int left,int right,int L,int R){
if(left>=L&&right<=R)return tree[rt];
int mid=(left+right)>>1,res=0;
if(L<=mid)res+=query(l[rt],left,mid,L,R);
if(mid<R)res+=query(r[rt],mid+1,right,L,R);
return res;
}
map <int,int> tid;
int check(__int128 x,int debug){
auto it=tid.upper_bound((x%k+k)%k);
int cnt=0;
int pos=upper_bound(a+1,a+1+n,x)-a;
if(it!=tid.end()){
int rid=it->second;
cnt=query(root[rid],1,n,pos,n);
}
//if(debug)cout<<"de "<<cnt<<"\n";
__int128 all=0;
if(x>=0)all=suf[pos]-(n-pos+1)*(x/k)+cnt;
else all=suf[pos]-(n-pos+1)*-((-x-1)/k+1)+cnt;
__int128 tmp=sum;
//if(debug)cout<<"de "<<tmp<<"\n";
tmp-=(all-(n-pos+1));
tmp=max(tmp,(__int128)0);
tmp=min(tmp,(__int128)n-pos+1);
//if(debug)cout<<"de "<<all<<" "<<tmp<<" "<<pos<<" "<<n-(tmp+pos-1)+1<<"\n";
return n-(tmp+pos-1)+1;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>a[i],id[i]=i;
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
b[i]=a[i]/k,c[i]=a[i]%k;
sort(id+1,id+1+n,cmp);
for(int i=1;i<=n;i++){
root[id[i]]=root[id[i-1]];
tid[c[id[i]]]=id[i];
update(root[id[i]],1,n,id[i]);
}
for(int i=n;i>=1;i--)
suf[i]=suf[i+1]+b[i];
while(m--){
string op;
cin>>op;
if(op=="C"){
cin>>t;
sum+=t;
}else{
cin>>x;
long long l=-1e18,r=1e18;
while(l<r){
int mid=(l+r)>>1;
if(check(mid,0)<=x){
r=mid;
}else{
l=mid+1;
}
}
cout<<l<<"\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 5 5 7 3 9 A 3 C 1 A 2 C 2 A 3