QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #263118 | #7627. Phony | ucup-team1321 | WA | 171ms | 61360kb | C++20 | 8.0kb | 2023-11-24 15:35:31 | 2023-11-24 15:35:33 |
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 print(int i,long long l,long long r)
{
if(!i) return;
if(l==r)
{
// cerr<<"find"<<l<<" "<<tree[i].cnt<<"\n";
return;
}
long long mid=(l+r)/2;
print(tree[i].ls,l,mid);
print(tree[i].rs,mid+1,r);
return;
}
void split(int x,int &y,long long l,long long r,int k)
{
if(!x)
{
y=0;
return;
}
if(!y) y=new_node();
if(l==r)
{
int val=tree[x].cnt;
tree[x].cnt=k,tree[y].cnt=val-k;
return;
}
long long mid=(l+r)/2;
if(k<=tree[tree[x].ls].cnt)
{
tree[y].rs=tree[x].rs;
tree[x].rs=0;
split(tree[x].ls,tree[y].ls,l,mid,k);
}
else
{
split(tree[x].rs,tree[y].rs,mid+1,r,k-tree[tree[x].ls].cnt);
}
push_up(x);
push_up(y);
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];
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;
// cerr<<"now"<<a[i]/k<<" "<<a[i]%k<<"\n";
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];
}
}
// cerr<<"ed"<<siz[tot]<<" "<<v[tot]<<" "<<now<<"\n";
}
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<<"sss"<<T.tree[T.rt[tot]].cnt<<"\n";
// cerr<<"val"<<siz[tot]-now-t+1<<" "<<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=0;
// cerr<<"sss"<<tot<<" "<<T.tree[T.rt[tot]].cnt<<"\n";
// cerr<<"----------\n";
// T.print(T.rt[tot],0,k-1);
// cerr<<"split"<<siz[tot]-now<<"\n";
T.split(T.rt[tot],nrt,0,k-1,siz[tot]-now);
// cerr<<"----------\n";
// T.print(T.rt[tot],0,k-1);
// cerr<<"----------\n";
// T.print(nrt,0,k-1);
// cerr<<"pre"<<T.rt[tot]<<" "<<T.tree[T.rt[tot]].cnt<<"\n";
// cerr<<"pre"<<nrt<<" "<<T.tree[nrt].cnt<<"\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);
// T.print(T.rt[tot],0,k-1);
// cerr<<"after"<<T.tree[T.rt[tot]].cnt<<"\n";
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);
// cerr<<"pos"<<pos<<" "<<val<<" "<<siz[pos]-(t-sum[tot-2]+sum[pos])+1<<"\n";
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;
}
/*
10 4 10
1 14 25 37 51 60 81 72 83 100
C 8
A 2
C 3
A 1
*/
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 13820kb
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: 13656kb
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: 0
Accepted
time: 2ms
memory: 13664kb
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 8200 2945 7647 7531 5291 5001 2042 4721 4721 6881 4097 7187 7218 7035 7018 811 6752 2561 6683 6114 6135 3581 5291 1485 5957 5393 2042 5303 5171 5205 4721 5084 4029 4097 4591 4816 4586 4705 2042 4535 4454 4603 4435 3581 4345 115 2042 4284 2042 4274 1485 4326 -17552
result:
ok 56 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 13840kb
input:
100 300 3453213 4777243 17293302 43453992 45342348 82151965 11360220 63630258 38237802 1 56066162 75020027 83365329 100659838 2141897 73421986 102600372 100824166 46869742 31931613 26168082 41399743 62249685 31666167 96044265 81576202 44039394 94271661 37319513 46613514 14176026 23991180 3310773 635...
output:
16238806 100824166 74028301 100824166 98702945 100659838 3066866 82151965 78167694 86340309 16238806 64926204 73585978 16238806 64926204 4777243 62249685 78951605 16238806 3066866 77853267 78427881 75980670 43453992 16238806 1 78122989 62404688 72949759 3310773 35761909 44960459 73552383 72045179 16...
result:
ok 159 lines
Test #5:
score: 0
Accepted
time: 4ms
memory: 15876kb
input:
10000 10000 424242 17989609 33305173 36700219 9019831 18836819 21791961 21965035 18824893 1921235 23926509 28110961 33993409 12966853 13082665 4452379 1637119 38371575 1826245 36931693 1 33924345 30310225 30503101 4578015 31263907 15733393 40333897 34523425 25601465 11528899 18236695 4978289 9301153...
output:
29899255 19256287 20728753 27691558 11569357 18782611 6940738 25519453 36411607 15396403 20282701 5151091 13921909 21284225 20657428 13921909 19561543 11116483 30447757 38758135 7394929 27457873 34310557 1419251 40938731 25617811 25928137 21610443 40849627 18524773 24971899 24506287 4463929 27691558...
result:
ok 4977 lines
Test #6:
score: 0
Accepted
time: 9ms
memory: 15688kb
input:
10000 10000 8633427 538078847 573328001 833039873 394897857 557339356 788138551 409068537 418595873 489365441 734786049 510598641 38313681 218800001 757899321 509729089 719587751 396447437 1228081 824921431 557992001 176123501 195314201 316694001 77352241 390252445 488382377 688760625 683480525 7293...
output:
741597921 684643385 244445841 679897197 788928601 972172681 949082401 473000401 79937561 724673651 683480525 854680935 660858076 235090570 532125856 394971761 439375061 765033025 256613601 932699581 712850809 553280433 133989601 529728321 79937561 753982913 438698461 756463614 719635425 653599361 78...
result:
ok 4974 lines
Test #7:
score: 0
Accepted
time: 3ms
memory: 13664kb
input:
10000 10000 234335 38273 570241 147447 980201 158871 620297 217341 747545 477489 864709 74921 933841 364881 763649 637606 388241 559121 571796 710541 375597 791873 796201 310895 217601 120001 347961 16001 719721 23281 502721 669601 42081 532097 525926 794801 841781 892801 487801 899921 847065 228801...
output:
872001 598031 77481 222769 54785 977985 400801 623201 239481 479121 641751 27641 637501 280769 587202 120001 353441 276561 205601 645169 205201 840423 842665 280001 619395 327041 261313 59801 741666 376 901021 633685 338241 815153 598031 547691 802993 832401 442001 280769 569121 434756 841441 735377...
result:
ok 4970 lines
Test #8:
score: 0
Accepted
time: 5ms
memory: 13664kb
input:
9864 10000 233 2321 4497 5656 4866 2321 2296 1173 785 9809 8021 3601 3676 3671 2001 8641 7921 4001 7851 5156 9961 5376 965 8176 5247 5681 3041 1201 1937 699 545 6001 9401 529 8393 9445 1601 961 51 5601 1 5329 4257 8001 2001 3161 2751 5889 6353 2473 6720 1421 4169 7201 1101 9521 9009 5921 5249 8761 7...
output:
5609 5049 8501 9751 6625 2351 6761 9041 2451 8561 6249 3099 4845 4401 3265 9416 9592 8001 9528 6009 9568 4241 8061 7871 2001 821 3793 703 5576 3265 5001 8365 9378 1981 1121 1441 9355 6401 561 3601 8601 5361 8811 4801 5377 3735 769 1496 401 2306 6451 241 8025 8376 6551 8705 3401 1 5281 1531 976 7185 ...
result:
ok 4952 lines
Test #9:
score: 0
Accepted
time: 171ms
memory: 61360kb
input:
500000 4 86 7389249156947561 9098507703019521 3864091904486041 6310459731705571 647583641047201 1621185944707376 7003000429904937 593897105426626 9875992015549861 6557342520948641 9526782645198001 6401373507717121 3893859617993451 4665953390717037 889563644563201 6303536850022463 4409281560689537 43...
output:
9776337802111349 1191089114896223
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 156ms
memory: 55164kb
input:
500000 4 38 6315784043021797 596519996425501 54280272213000001 25297014706267501 381135807724572001 1562706443227627 12734737545675181 48209123950130251 210066342820346881 11997568254816001 1328078731348513 7836814573901041 145542395686987153 35504248422218626 3019601348227201 441053811513439741 227...
output:
927406470830660237 26771400341427457
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 2ms
memory: 11600kb
input:
1000 1000 30 4288386677374751 2662519464063971 4420636922012714 1205174734895841 5180156019151001 2693464561053401 1639891393987585 4195001110670401 6591575153723641 4835655971249743 8713497968125113 4361863383313001 9458730022038216 195078418495057 9840542551744851 4279436254933176 228287227132113 ...
output:
2580641985266797 1324532342145969 699248987828633 1010825796405001 415254197223673 4437530592262803 8698057636492001 3294284903690863 7479153211415601 2533180893181505 7778707561448995 3294284903690863 2562505687756801 3932218574465861 5933603589438393 9714884423972426 6541188010486880 6695513869117...
result:
ok 492 lines
Test #12:
score: 0
Accepted
time: 0ms
memory: 13840kb
input:
1000 1000 20 13488374345924801 43610227415330311 2809367337504001 55479626248453921 46769838945139126 43792160864601601 31136925209007223 50701143722818513 20372262029027761 44373489892234721 45444219805100721 19250473390433001 24306584421061801 6631609709598721 48119896722940561 5506928429719201 61...
output:
49243684713094401 80511583135737601 43868258458230753 24470961950774086 58871193301701481 21244892632911361 61855037591352341 53852795162052481 11687618439170101 99250681772700161 43561491591910701 5353066467314821 1392491209412161 58435920489024396 51571596551244001 19673630481159601 10664493472993...
result:
ok 504 lines
Test #13:
score: -100
Wrong Answer
time: 0ms
memory: 11580kb
input:
1000 1000 1000000000000 76723071693841 4001941589666283 4076282713984577 6234887627733381 4897638660755449 2328368250736040 196595968770531 7992824401757137 7795120279050241 2773491889005001 1966967217456876 2364594270616769 1920097794021701 7810375092696225 546469103980101 9613327462804837 31385262...
output:
result:
wrong answer 1st lines differ - expected: '6952394964626161', found: ''