QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #262917 | #7627. Phony | ucup-team1321 | WA | 2ms | 13980kb | C++20 | 7.0kb | 2023-11-24 12:53:11 | 2023-11-24 12:53:11 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
const int N=500005;
int n,m,k;
long long a[N];
long long v[N],tot;
struct Segment_Tree
{
struct Node
{
int ls,rs;
int cnt;
}tree[N*70];
int tot;
int rt[N];
Segment_Tree():tot(0)
{
memset(rt,0,sizeof(rt));
}
int new_node()
{
int now=++tot;
tree[now].ls=tree[now].rs=0;
tree[now].cnt=0;
return now;
}
void push_up(int i)
{
tree[i].cnt=tree[tree[i].ls].cnt+tree[tree[i].rs].cnt;
return;
}
void modify(int &i,long long l,long long r,long long u,long long v)
{
if(!i) i=new_node();
if(l==r)
{
tree[i].cnt+=v;
return;
}
long long mid=(l+r)/2;
if(u<=mid) modify(tree[i].ls,l,mid,u,v);
else modify(tree[i].rs,mid+1,r,u,v);
push_up(i);
return;
}
int merge(int u,int v,long long l,long long r)
{
if(!u) return v;
if(!v) return u;
if(l==r)
{
tree[u].cnt+=tree[v].cnt;
return u;
}
long long mid=(l+r)/2;
tree[u].ls=merge(tree[u].ls,tree[v].ls,l,mid);
tree[u].rs=merge(tree[u].rs,tree[v].rs,mid+1,r);
push_up(u);
return u;
}
void split(int i,long long l,long long r,int k,int &x,int &y)
{
if(!i)
{
x=y=0;
return;
}
if(l==r)
{
x=i;
y=new_node();
tree[x].cnt=k,tree[y].cnt=tree[i].cnt-k;
return;
}
long long mid=(l+r)/2;
if(k<=tree[tree[i].ls].cnt)
{
y=i;
split(tree[i].ls,l,mid,k,x,tree[y].ls);
}
else
{
x=i;
split(tree[i].rs,mid+1,r,k-tree[tree[i].ls].cnt,tree[x].rs,y);
}
push_up(i);
return;
}
long long findkth(int i,long long l,long long r,int k)
{
if(!i) return 0;
if(l==r) return l;
long long mid=(l+r)/2;
if(k<=tree[tree[i].ls].cnt) return findkth(tree[i].ls,l,mid,k);
else return findkth(tree[i].rs,mid+1,r,k-tree[tree[i].ls].cnt);
}
long long findkth(int u,int v,long long l,long long r,int k)
{
if(l==r) return l;
long long mid=(l+r)/2;
if(k<=tree[tree[u].ls].cnt+tree[tree[v].ls].cnt) return findkth(tree[u].ls,tree[v].ls,l,mid,k);
else return findkth(tree[u].rs,tree[v].rs,mid+1,r,k-tree[tree[u].ls].cnt-tree[tree[v].ls].cnt);
}
}T;
int siz[N],sum[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
v[++tot]=a[i]/k;
sort(v+1,v+tot+1);
tot=unique(v+1,v+tot+1)-v-1;
for(int i=1;i<=n;i++)
{
int p=lower_bound(v+1,v+tot+1,a[i]/k)-v;
T.modify(T.rt[p],0,k-1,a[i]%k,1);
siz[p]++;
}
for(int i=1;i<=tot;i++)
sum[i]=sum[i-1]+siz[i];
int now=0;
while(m--)
{
char ch;
long long t;
cin>>ch>>t;
if(ch=='C')
{
while(t>0)
{
if(t<siz[tot]-now) now+=t,t=0;
else if(now>0)
{
t-=siz[tot]-now;
now=0;
v[tot]--;
if(tot-1>=1&&v[tot]==v[tot-1])
{
// cerr<<"merge"<<v[tot]<<"\n";
T.rt[tot-1]=T.merge(T.rt[tot-1],T.rt[tot],0,k-1);
siz[tot-1]+=siz[tot];
tot--;
sum[tot]=sum[tot-1]+siz[tot];
}
}
if(t==0) break;
long long del=t/siz[tot];
if(tot-1>=1) del=min(del,v[tot]-v[tot-1]);
v[tot]-=del;
t-=del*siz[tot];
if(tot-1>=1&&v[tot]==v[tot-1])
{
// cerr<<"merge"<<v[tot]<<"\n";
T.rt[tot-1]=T.merge(T.rt[tot-1],T.rt[tot],0,k-1);
siz[tot-1]+=siz[tot];
tot--;
sum[tot]=sum[tot-1]+siz[tot];
}
}
}
else if(ch=='A')
{
// cerr<<"siz"<<siz[tot]<<" "<<now<<"\n";
if(t<=siz[tot]-now)
{
long long val=T.findkth(T.rt[tot],0,k-1,siz[tot]-now-t+1);
// cerr<<"val"<<val<<"\n";
cout<<v[tot]*k+val<<"\n";
continue;
}
else t-=siz[tot]-now;
// cerr<<"now"<<t<<"\n";
if(tot-1>=1&&v[tot]==v[tot-1]+1)
{
// cerr<<"tonext\n";
if(t<=siz[tot-1]+now)
{
int nrt;
// cerr<<"sss"<<tot<<" "<<T.tree[T.rt[tot]].cnt<<"\n";
T.split(T.rt[tot],0,k-1,siz[tot]-now,T.rt[tot],nrt);
// cerr<<"split"<<siz[tot]-now<<"\n";
// cerr<<"sss"<<T.tree[T.rt[tot]].cnt<<"\n";
// cerr<<"sss"<<T.tree[nrt].cnt<<"\n";
// cerr<<"kkk"<<siz[tot-1]+now-t+1<<"\n";
long long val=T.findkth(T.rt[tot-1],nrt,0,k-1,siz[tot-1]+now-t+1);
cout<<v[tot-1]*k+val<<"\n";
T.rt[tot]=T.merge(T.rt[tot],nrt,0,k-1);
continue;
}
else t-=siz[tot-1]+now;
// cerr<<"Ret"<<t<<"\n";
int l=1,r=tot-2,pos=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(sum[tot-2]-sum[mid-1]>=t) pos=mid,l=mid+1;
else r=mid-1;
}
long long val=T.findkth(T.rt[pos],0,k-1,siz[pos]-(t-sum[tot-2]-sum[pos])+1);
cout<<v[pos]*k+val<<"\n";
}
else
{
if(t<=now)
{
long long val=T.findkth(T.rt[tot],0,k-1,siz[tot]-t+1);
cout<<(v[tot]-1)*k+val<<"\n";
continue;
}
else t-=now;
cerr<<"ret"<<t<<"\n";
int l=1,r=tot-1,pos=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(sum[tot-1]-sum[mid-1]>=t) pos=mid,l=mid+1;
else r=mid-1;
}
long long val=T.findkth(T.rt[pos],0,k-1,siz[pos]-(t-sum[tot-1]+sum[pos])+1);
cout<<v[pos]*k+val<<"\n";
}
//
}
}
return 0;
}
/*
5 1 8
294 928 293 392 719
A 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13980kb
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: 2ms
memory: 13884kb
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: 2ms
memory: 13892kb
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:
6757 9161 4660 8200 2796 7647 7531 5126 4893 1864 4660 4660 6757 3961 7187 7218 7035 7018 699 6752 2330 6735 6140 6058 3495 5126 1398 6022 5359 1864 5344 5126 5302 4660 4893 3961 3961 4659 4660 4659 4768 1864 4629 4488 4427 4435 3495 4422 0 1864 4371 1864 4371 1398 4406 -17500
result:
wrong answer 1st lines differ - expected: '6881', found: '6757'