QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#276103#7627. PhonyYu_JieAC ✓213ms56272kbC++142.6kb2023-12-05 16:23:322023-12-05 16:23:32

Judging History

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

  • [2023-12-05 16:23:32]
  • 评测
  • 测评结果:AC
  • 用时:213ms
  • 内存:56272kb
  • [2023-12-05 16:23:32]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
typedef __int128 LL;
using namespace std;
const int N=500005;
int n,m,row,col,b[N],c[N];
ll a[N],k,mpr[N],mpc[N];
LL tim[N],ctm;
vector<int> vc[N];
struct bit {
    int a[N];
    void add(int x) {for(x=col-x+1;x<=col;x+=x&-x) a[x]++;}
    int ask(int k) {
        int x=0;
        for(int i=1<<__lg(col);i;i>>=1) if(x+i<=col&&a[x+i]<k) k-=a[x+=i];
        return col-x;
    }
} tr;
ll read() {
	ll x=0; char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='C'||c=='A') return c=='C';
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
	return x;
}
int main() {
    n=read(); m=read(); k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1,[](ll x,ll y){return x>y;});
    for(int i=1;i<=n;i++) mpr[i]=a[i]/k;
    sort(mpr+1,mpr+n+1); row=unique(mpr+1,mpr+n+1)-mpr-1;
    for(int i=1;i<=n;i++) b[i]=lower_bound(mpr+1,mpr+row+1,a[i]/k)-mpr;
    for(int i=1;i<=n;i++) mpc[i]=a[i]%k;
    sort(mpc+1,mpc+n+1); col=unique(mpc+1,mpc+n+1)-mpc-1;
    for(int i=1;i<=n;i++) c[i]=lower_bound(mpc+1,mpc+col+1,a[i]%k)-mpc;
    for(int i=1;i<=n;i++) vc[b[i]].push_back(c[i]);
    for(int i=row,j=0;i>=1;j+=vc[i].size(),i--) {
        sort(vc[i].begin(),vc[i].end());
        tim[i]=tim[i+1]+(LL)j*(mpr[i+1]-mpr[i]);
    }
    for(int i:vc[row]) tr.add(i);
    for(int i=row,sz=vc[row].size(),re=0;m--;) {
        if(read()) {
            ll x=read();
            ctm+=x;
            for(;i>1&&ctm>=tim[i-1];i--) {
                re=0;
                for(int j:vc[i-1]) tr.add(j),sz++;
            }
            if(i>1&&ctm-tim[i]>(mpr[i]-mpr[i-1]-1)*sz) {
                if(!re) {
                    re=sz;
                    x=ctm-tim[i]-(mpr[i]-mpr[i-1]-1)*sz;
                }
                re-=x;
                int y=tr.ask(sz-re);
                while(vc[i-1].size()&&vc[i-1].back()>=y) {
                    sz++; tr.add(vc[i-1].back());
                    vc[i-1].pop_back();
                }
            }
        }
        else {
            int x=read();
            if(x>sz) {printf("%lld\n",a[x]); continue;}
            ll ans;
            if(!re) {
                if(x<=sz-(ctm-tim[i])%sz) ans=(mpr[i]-(ctm-tim[i])/sz)*k+mpc[tr.ask((ctm-tim[i])%sz+x)];
                else ans=(mpr[i]-(ctm-tim[i]+sz-1)/sz)*k+mpc[tr.ask(((ctm-tim[i])%sz+x-1)%sz+1)];
            }
            else {
                if(x<=re) ans=(mpr[i-1]+1)*k+mpc[tr.ask(sz-re+x)];
                else ans=(mpr[i-1])*k+mpc[tr.ask(x-re)];
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 26304kb

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: 5ms
memory: 28288kb

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: 0ms
memory: 28540kb

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: 26236kb

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: 3ms
memory: 28380kb

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: 3ms
memory: 28376kb

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: 0ms
memory: 26656kb

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: 7ms
memory: 28336kb

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: 125ms
memory: 55600kb

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: 117ms
memory: 55248kb

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: 0ms
memory: 26224kb

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: 28396kb

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: 0
Accepted
time: 2ms
memory: 28320kb

input:

1000 1000 1000000000000
76723071693841 4001941589666283 4076282713984577 6234887627733381 4897638660755449 2328368250736040 196595968770531 7992824401757137 7795120279050241 2773491889005001 1966967217456876 2364594270616769 1920097794021701 7810375092696225 546469103980101 9613327462804837 31385262...

output:

6952394964626161
7158352910024521
4149497765479601
9900953799914401
6419336517919201
9746224015077633
5346098525649991
5235647031944561
3335542892699776
5512227247130913
8616652091500801
1397278980044521
3841490033058049
517377148765233
8986270059616353
9838827631751897
9746224015077633
566686874293...

result:

ok 481 lines

Test #14:

score: 0
Accepted
time: 2ms
memory: 28336kb

input:

1000 1000 9
736190983533903 21719078292842113 46483386833927161 116845585897639969 57372082975501 10208324490361201 40496604131910928 1143694379275001 24491110306371745 55132215575065201 4778428777389499 223766502907940389 1184377886496001 98642065849744033 122049543083480741 23459277274737337 46718...

output:

21897112623559681
37080138072007585
28645906737049687
93563878098028801
1080487262335105
201061338619564801
217229002478914581
880267403051779
25891167708498601
85997700487083457
11652132984688693
433884925137665
868109548100029591
28645906737049687
3578386959453538
147145059396878401
68154726135387...

result:

ok 494 lines

Test #15:

score: 0
Accepted
time: 28ms
memory: 26264kb

input:

100 500000 42
96796405033128001 60895589598071041 1050077981665153 1569849425782657 48291519784436371 65764961790951281 251362888799823531 10359911976952825 43105647049195501 101425264762685761 34701448521431251 124622989725395701 220421477915908732 41282561617180129 28632353931512929 33891896604714...

output:

551576251694933011
3898179570663745
152047504158090113
50316735415106161
551576159814486325
25130820088175257
551574644299354831
50316735415106161
4052199316055152
551572957811356825
41282561617180129
103046968965900961
67136254551552330
1569849425782657
101425264762685761
25130820088175257
31963355...

result:

ok 248318 lines

Test #16:

score: 0
Accepted
time: 32ms
memory: 28380kb

input:

100 500000 72381
15283903812856849 92168973158920705 12503976457087025 15157271357568451 55504514613970241 401712784408041 333573890917987201 392507710432575409 1219660186932001 34051773652954201 1493430260750065 796573935587305 57936004495197256 8315085261208321 63354650964003151 26000421681401476 ...

output:

22900778668463473
18035459797992001
474675641665275097
474675641665275097
474675641665275097
8358655230222145
474675641665275097
474675374753027116
26687595979896251
26687595979896251
474674465898684424
1672963426575361
15283903812856849
12009920545846081
474672669326336755
34051773652954201
2290077...

result:

ok 248342 lines

Test #17:

score: 0
Accepted
time: 144ms
memory: 56272kb

input:

500000 500000 24
26204990905601 42821071736677 30277533879661 35060856467801 17282781925921 31374560060596 24409699464601 11776097945281 8253239646865 47621419106281 35031948956679 14225503032409 7616229246209 24704924967201 13825198072001 2076352544041 2414194406881 5134796552494 12603589360225 131...

output:

28100746188001
21486969013351
36035304511711
38012084135761
5447387686041
29396368922311
19014703378201
2670923217001
36873296026237
5066139976081
5745153317193
17215143483001
40074957223477
46451400352769
6622996371001
4599638103101
14468630833681
117909440857
31892198639745
41357776323751
27376414...

result:

ok 248304 lines

Test #18:

score: 0
Accepted
time: 142ms
memory: 55816kb

input:

500000 500000 8
7852524359169 10874653205581 14214586754537 11589605524001 7905958933331 4723078001729 8472495995273 14933104687139 11192952607901 478844247373 7261580825548 11237644745931 11189148253377 13896590039681 11630676366481 1121214267905 2021342874401 6163795609815 237869577769 73833217065...

output:

6948877459201
8668520092656
1958170358801
7301034075105
722592592801
3308097849461
10745987232198
15747472033377
2813889981521
4639866456977
6663273035137
6174241884769
15328559295451
2908840270451
10687522075681
12746695898181
10928636296715
7605707069441
10292409479701
2271418974205
7310377747905
...

result:

ok 248328 lines

Test #19:

score: 0
Accepted
time: 177ms
memory: 55956kb

input:

500000 500000 2223
958820062786561 3023867295955153 4237889053452001 3784651936024051 3253939070428801 582674124114001 1291355865312751 4417061587859269 1457411514423601 1545632802676873 3446866726687801 3605077514623033 3073997096478529 88505243918785 1356134687782169 3622752946705537 4342606756458...

output:

1047744885744897
2505169883520001
2270251858884321
1198559168867841
4116625132082689
4202572758117025
1491203870310337
3510315263304649
2570272352934265
3259840078550846
168913204736001
872727699842857
2599071538201321
3621740586682454
3553690807555021
1168241718850561
3359633148933751
2010690295732...

result:

ok 248293 lines

Test #20:

score: 0
Accepted
time: 186ms
memory: 56216kb

input:

500000 500000 5246
8932030541612201 3159955653335201 4080421880864001 986425003746001 4048386638075081 4618673308237801 563483477689681 1776752186578201 202256694320257 8103437911752937 1910367624785145 3572988250547821 6777415019087985 8343607075590401 1285610287791933 3160774828736321 918257320523...

output:

6017602686133801
812524570852001
10471043427268321
1141203366158537
145588315692457
5879163323661889
5954552627511105
4068046175616001
1143296598707601
5295135074144641
8829000186327031
4545739749833553
3043435190160769
1214580310304401
6913215449701
8990113463260111
3795412281811281
947681044728329...

result:

ok 248300 lines

Test #21:

score: 0
Accepted
time: 213ms
memory: 55244kb

input:

500000 500000 84423
20657955624377281 70241986792321 115759741006567213 17219258586053261 667595324087420 67513891991975425 72241897058379491 21477200139871905 111160537054130776 155347098210200961 8351687319130717 10623613777890202 5619677221440001 46385448358705381 2210780451720521 389387598352896...

output:

34892442793752589
1624080281553241
67934051466700915
9494886044480761
80722067537357401
154044439729112321
46621021533445633
91702950487905505
995219008906241
8575840134800641
115531459584271834
308807230615951
17975548020473569
42410907299945972
112109568468961
140018061526004341
11075163635550025
...

result:

ok 248315 lines

Test #22:

score: 0
Accepted
time: 167ms
memory: 55880kb

input:

500000 500000 89
69013181336697 103417228776481 15569702091749 34022176495421 31677233338121 78464451159521 55524610634945 89315402840091 94917504272191 74220720180929 33922964346161 91048891264987 4631128572001 145540732068269 127786782830081 90486047387189 17140147501601 70909316468217 94432514880...

output:

125556456786891
83080012093041
149100180770473
2687481548801
59543347990941
5362000988161
3877910355969
81408863898241
116321565930097
169823551215441
160013995304397
116848249994337
141636627921921
78972591191001
143150111775421
167950556727777
111825207498497
34972927250001
89591521354945
16764742...

result:

ok 248305 lines

Extra Test:

score: 0
Extra Test Passed