QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#65898	#3042. Hilbert's Hotel	gyh20	TL	136ms	21564kb	C++14	2.2kb	2022-12-04 11:02:38	2022-12-04 11:02:40

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-12-04 11:02:40]
评测

测评结果：TL
用时：136ms
内存：21564kb

查看

[2022-12-04 11:02:38]
提交

answer

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
	re int t=0;re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
	return t;
}
const int M=1e9+7;
inline void add(re int &x,re int y){(x+=y)>=M?x-=M:x;}
inline int Mod(re int x){return x>=M?x-M:x;}
inline int ksm(re int x,re int y){
	re int s=1;
	while(y){
		if(y&1)s=1ll*s*x%M;
		x=1ll*x*x%M,y>>=1;
	}
	return s;
}
int n,tg1[1200002],tg2[1200002],lst[1200002],G,X,ID[300002];
long long sum[1200002];
inline void build(re int p,re int l,re int r){
	tg1[p]=1,tg2[p]=0;
	if(l==r)return;
	re int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
inline void Mul(re int p,re int x,re int y){
	tg1[p]=1ll*tg1[p]*x%M,tg2[p]=1ll*tg2[p]*x%M;
	add(tg2[p],y);
}
inline void pd(re int p){
	if(tg1[p]!=1||tg2[p])Mul(p<<1,tg1[p],tg2[p]),Mul(p<<1|1,tg1[p],tg2[p]),tg1[p]=1,tg2[p]=0;
}
inline void mul(re int p,re int l,re int r,re int x,re int y,re int z1,re int z2){
	if(l>=x&&r<=y){
		if(z1)add(tg1[p],tg1[p]),add(tg2[p],tg2[p]);
		add(tg2[p],z2);return;
	}re int mid=l+r>>1;pd(p);
	if(x<=mid)mul(p<<1,l,mid,x,y,z1,z2);
	if(y>mid)mul(p<<1|1,mid+1,r,x,y,z1,z2);
}
inline void ask(re int p,re int l,re int r,re int x){
	if(l==r){
		X=1ll*X*tg1[p]%M,add(X,tg2[p]);
		return;
	}re int mid=l+r>>1;pd(p);
	if(x<=mid)ask(p<<1,l,mid,x);
	else ask(p<<1|1,mid+1,r,x);
}
int main(){
	n=read(),build(1,0,n);
	for(re int i=1;i<=n;++i){
		re int o=read();sum[i]=sum[i-1],lst[i]=lst[i-1];
		if(o==1){
			int x=read();++G,ID[i]=G;
			if(x==0)lst[i]=i,mul(1,0,n,0,G,1,0),mul(1,0,n,G,G,0,1);
			else sum[i]=sum[i-1]+x,mul(1,0,n,0,G-1,0,x);
		}
		else if(o==2){
			re int x=read();X=read()-1;
			ask(1,0,n,x),printf("%d\n",X);
		}
		else{
			re int v=read(),pos=i;
			while(1){
				if(pos<=0){
					puts("0");
					break;
				}
				re int x=lst[pos];
				if(sum[pos]-sum[x]>v){
					re int l=x,r=pos-1,oo=x;
					while(l<=r){
						re int mid=l+r>>1;
						if(sum[pos]-sum[mid]>v)oo=mid,l=mid+1;
						else r=mid-1;
					}
					printf("%d\n",ID[oo+1]);
					break;
				}
				else{
					v-=(sum[pos]-sum[x]);
					if(v&1){
						printf("%d\n",ID[x]);break;
					}v>>=1;
					pos=x-1;
				}
			}
		}
	}
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 9548kb

input:

output:

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 3ms

memory: 7504kb

input:

output:

result:

ok 12 lines

Test #3:

score: 0

Accepted

time: 1ms

memory: 7504kb

input:

output:

result:

ok 8 lines

Test #4:

score: 0

Accepted

time: 2ms

memory: 9616kb

input:

output:

result:

ok 13 lines

Test #5:

score: 0

Accepted

time: 1ms

memory: 9680kb

input:

output:

result:

ok 6 lines

Test #6:

score: 0

Accepted

time: 5ms

memory: 7592kb

input:

output:

result:

ok 12 lines

Test #7:

score: 0

Accepted

time: 5ms

memory: 7752kb

input:

output:

result:

ok 9 lines

Test #8:

score: 0

Accepted

time: 6ms

memory: 9548kb

input:

output:

result:

ok 7 lines

Test #9:

score: 0

Accepted

time: 6ms

memory: 7580kb

input:

output:

result:

ok 9 lines

Test #10:

score: 0

Accepted

time: 3ms

memory: 9556kb

input:

output:

result:

ok 8 lines

Test #11:

score: 0

Accepted

time: 3ms

memory: 7556kb

input:

output:

result:

ok 13 lines

Test #12:

score: 0

Accepted

time: 5ms

memory: 9560kb

input:

output:

result:

ok 12 lines

Test #13:

score: 0

Accepted

time: 2ms

memory: 7524kb

input:

output:

result:

ok 652 lines

Test #14:

score: 0

Accepted

time: 2ms

memory: 7516kb

input:

output:

result:

ok 607 lines

Test #15:

score: 0

Accepted

time: 4ms

memory: 7520kb

input:

output:

result:

ok 609 lines

Test #16:

score: 0

Accepted

time: 5ms

memory: 9716kb

input:

output:

result:

ok 613 lines

Test #17:

score: 0

Accepted

time: 8ms

memory: 7568kb

input:

output:

result:

ok 656 lines

Test #18:

score: 0

Accepted

time: 0ms

memory: 7572kb

input:

output:

result:

ok 611 lines

Test #19:

score: 0

Accepted

time: 5ms

memory: 7600kb

input:

output:

result:

ok 602 lines

Test #20:

score: 0

Accepted

time: 3ms

memory: 7520kb

input:

output:

result:

ok 626 lines

Test #21:

score: 0

Accepted

time: 4ms

memory: 9564kb

input:

output:

result:

ok 644 lines

Test #22:

score: 0

Accepted

time: 1ms

memory: 7588kb

input:

output:

result:

ok 687 lines

Test #23:

score: 0

Accepted

time: 103ms

memory: 17196kb

input:

285800
1 589
2 1 115
2 1 226
2 1 514
2 1 456
3 629709122
1 619
2 2 192
3 459147753
1 38
2 2 576
2 3 8
3 201981823
3 524189144
2 3 32
1 56
2 4 20
3 214735859
1 890
2 5 636
3 478695264
3 460825804
2 5 103
3 952035202
2 0 286
1 525
1 288
1 957
2 0 618
3 735607495
2 1 93
2 1 286
1 985
2 9 663
1 683
2 2 ...

output:

result:

ok 190990 lines

Test #24:

score: 0

Accepted

time: 86ms

memory: 19064kb

input:

291729
1 894
1 890
3 802126177
3 272286217
1 0
2 1 374
3 891152646
1 820
2 2 147
1 310
3 46206280
2 4 808
3 18706394
2 1 331
3 664920704
2 1 654
2 0 748
3 192123924
3 708982947
3 220679626
3 704888628
1 160
3 964332875
3 169548294
3 662085712
3 515358639
3 958291113
3 383486479
2 4 124
1 392
1 239
3...

output:

result:

ok 194496 lines

Test #25:

score: 0

Accepted

time: 79ms

memory: 17516kb

input:

284878
1 658
1 878
1 399
2 0 139
1 36
2 2 769
1 823
2 3 335
3 383102579
1 735
2 2 460
3 907616047
3 165176802
2 1 219
3 425702053
3 428981593
1 721
2 0 39
3 727162062
1 477
1 311
2 2 562
3 451950835
3 65057699
1 710
1 712
2 6 339
3 7344432
2 2 628
1 75
1 978
3 19967679
1 97
1 402
3 160663473
1 702
3...

output:

result:

ok 189957 lines

Test #26:

score: 0

Accepted

time: 106ms

memory: 18700kb

input:

294009
3 967557698
1 914
1 302
3 745869808
3 990025222
1 998
1 310
3 173316754
2 2 134
2 1 212
2 0 3
3 974856036
2 1 306
1 176
1 252
3 469723561
3 809790361
3 131203832
2 5 114
2 3 329
2 3 627
3 609236246
2 0 80
1 788
1 961
3 223398965
1 899
2 2 45
1 466
3 857489318
2 6 103
1 686
3 717426508
3 18954...

output:

result:

ok 196252 lines

Test #27:

score: 0

Accepted

time: 69ms

memory: 18500kb

input:

282562
2 0 74
3 17540587
3 68688373
2 0 562
3 593200593
1 850
3 850964180
2 1 606
1 849
2 0 994
1 793
1 8
1 19
2 3 285
1 936
1 945
3 897195209
3 689162617
3 432243973
2 6 597
3 513148040
2 7 575
2 6 501
2 4 5
1 481
2 0 437
2 7 835
3 782722001
1 974
2 1 271
1 109
1 0
2 3 151
1 250
2 12 5
3 569019713
...

output:

result:

ok 188785 lines

Test #28:

score: 0

Accepted

time: 90ms

memory: 18616kb

input:

293374
1 225
3 447206486
2 0 878
1 827
1 194
3 390633943
3 360374143
3 637018590
3 951750234
1 0
2 3 71
3 526531042
1 66
1 835
2 1 225
1 0
3 531166748
3 609646428
2 6 825
3 281460658
2 4 438
3 722590971
3 436988302
3 107135791
1 449
2 4 953
1 404
1 733
1 380
2 0 436
1 837
3 747811327
2 9 264
3 61480...

output:

result:

ok 195658 lines

Test #29:

score: 0

Accepted

time: 85ms

memory: 19564kb

input:

287143
3 402401437
2 0 394
1 93
3 644955565
1 606
2 0 840
3 697316701
1 657
3 482937747
3 844029157
2 1 54
2 0 669
3 162399854
2 2 461
2 1 88
1 62
1 490
2 3 359
1 320
1 348
2 3 396
1 391
1 486
2 0 984
3 126661122
2 8 116
1 774
2 4 24
3 366371654
3 695192494
1 86
3 885892130
3 860516461
2 11 64
3 794...

output:

result:

ok 191311 lines

Test #30:

score: 0

Accepted

time: 108ms

memory: 18860kb

input:

282111
3 312193607
2 0 560
1 664
3 4141348
1 107
2 2 89
1 196
3 224802799
1 0
3 513505207
3 258517554
1 722
2 2 4
2 4 17
3 333760602
2 0 701
2 3 103
2 3 71
1 48
1 44
3 342943369
2 7 19
2 7 35
3 567363618
3 536126078
1 85
2 5 170
1 810
3 453599856
3 701607165
2 5 49
3 498442155
1 374
2 8 60
2 1 341
1...

output:

result:

ok 188398 lines

Test #31:

score: 0

Accepted

time: 136ms

memory: 18880kb

input:

292901
1 701
3 91197427
2 1 626
3 434122436
1 175
1 22
1 369
2 3 12
2 3 22
2 2 58
1 566
3 417019594
2 3 3
1 110
3 213369210
1 921
1 483
1 597
2 4 169
1 415
1 847
3 297474705
1 301
1 2
1 762
2 14 724
2 12 187
2 8 20
2 7 549
2 10 237
3 503174622
2 2 14
3 51110086
1 864
3 433753526
2 15 237
1 650
1 249...

output:

result:

ok 195292 lines

Test #32:

score: 0

Accepted

time: 91ms

memory: 18556kb

input:

285160
2 0 430
2 0 118
2 0 314
3 519690597
1 0
2 1 398
3 488819169
2 1 167
1 230
3 987277461
3 536897357
2 1 256
1 222
1 356
2 0 142
3 51827303
1 0
3 727040389
2 1 682
3 805524180
1 582
3 151359420
1 594
2 2 121
2 5 151
3 973152736
3 490971920
2 6 304
3 637107033
3 118697284
3 411400129
1 772
3 7126...

output:

result:

ok 189971 lines

Test #33:

score: 0

Accepted

time: 111ms

memory: 19956kb

input:

300000
2 0 206645902
3 636812873
1 997512702
2 0 239322423
2 0 504136008
2 1 804093075
3 371921677
2 0 328983963
1 283098207
3 348255721
2 0 11511005
2 0 520395076
3 984652715
1 705801389
2 0 739168623
1 92371913
3 808770816
3 281469617
2 2 129064647
1 664544935
2 2 255494310
1 65295784
1 666122355
...

output:

result:

ok 199761 lines

Test #34:

score: 0

Accepted

time: 106ms

memory: 18664kb

input:

300000
2 0 120279522
3 350149205
2 0 390226062
3 984974390
1 175531397
3 522290584
3 272836570
3 361541789
1 864564256
3 515741840
2 1 81980960
1 97952445
1 789323372
2 1 16283106
2 4 103627583
2 0 220863137
3 100436006
3 75300432
3 742403730
1 9918517
3 394132489
3 909010525
2 5 9549632
2 1 1270131...

output:

result:

ok 199688 lines

Test #35:

score: 0

Accepted

time: 95ms

memory: 18412kb

input:

300000
1 392932082
3 989370668
3 131336184
2 0 932448145
3 592769392
2 0 63265356
3 193566892
1 491988188
3 736803473
1 0
3 98125290
1 643060748
1 414422196
1 720853393
3 818013412
1 666255954
3 720870569
1 868901045
3 695636669
3 130792954
3 229856724
2 7 118932827
1 22323720
1 515683361
2 9 352599...

output:

result:

ok 199798 lines

Test #36:

score: 0

Accepted

time: 88ms

memory: 18324kb

input:

300000
2 0 865179181
1 849733455
1 475888606
3 664764837
2 0 502122289
2 1 54621192
2 0 44654453
3 454734650
1 483168419
2 3 114508904
3 204936692
2 2 212477296
2 2 255869005
3 146069567
2 0 364340874
3 712328661
3 976844988
2 2 125622460
1 879501567
1 474840102
2 2 461660105
3 361717108
1 481467299...

output:

result:

ok 200090 lines

Test #37:

score: 0

Accepted

time: 97ms

memory: 18616kb

input:

300000
3 65025048
3 300471686
3 262389793
1 617974611
3 888367034
2 0 643745991
2 0 34898350
2 1 209842882
1 728846510
3 316382357
3 337898147
3 251180716
1 192261125
3 343599429
2 2 296738763
2 3 119276772
1 198908858
1 43967128
3 319152449
1 593941774
3 419849297
1 224997097
2 5 9693486
2 4 169802...

output:

result:

ok 200018 lines

Test #38:

score: 0

Accepted

time: 119ms

memory: 21448kb

input:

300000
3 721612090
3 383268924
2 0 738487279
1 455617699
2 1 53299807
2 1 447484597
1 243117900
1 870985999
1 24956759
2 1 363456497
1 696069584
3 170877944
2 4 7084374
3 454741274
2 0 664175323
3 411689910
1 99054412
2 1 304324175
1 277918896
1 945275798
3 226625333
1 568562109
2 3 408661738
1 3860...

output:

result:

ok 200194 lines

Test #39:

score: 0

Accepted

time: 103ms

memory: 19528kb

input:

300000
2 0 229734167
3 516616837
2 0 873676738
1 613454867
2 1 112582151
3 917963654
3 44975290
1 947378995
2 0 548865020
1 64171679
2 1 44386465
2 1 580086701
3 562014742
1 270319374
3 537354903
3 492174569
3 672530186
3 756510589
1 587943012
3 559767067
2 3 2518010
2 0 360286604
1 427226225
1 4788...

output:

229734166
0
873676737
112582150
0
1
109698867
55937131
591637367
2
2
2
2
2
5
860780395
843554516
91343130
177241392
746289135
6
7
7
605496854
177273219
845808994
10
10
10
10
10
155532706
12
11
11
80491445
531424747
19
23
23
26
347947262
201421475
29
411353565
474233956
27
300272321
93183888
90542867...

result:

ok 199672 lines

Test #40:

score: 0

Accepted

time: 106ms

memory: 21564kb

input:

300000
1 0
2 1 51915217
1 198869845
2 1 706361597
1 368729873
2 2 142534910
2 0 487029464
2 2 149567297
3 167181073
3 675573463
2 1 301004347
2 2 155785193
1 799179729
3 327100630
1 516849406
3 110113660
2 3 8031182
3 860651400
3 119624178
2 4 536229091
2 0 391342072
3 323914421
2 2 15707957
1 21165...

output:

result:

ok 200263 lines

Test #41:

score: 0

Accepted

time: 129ms

memory: 21376kb

input:

300000
2 0 633299343
2 0 371195521
1 161261123
3 932744847
2 0 817373221
3 634766548
3 566480227
2 1 150951303
1 696226789
2 0 761657306
2 0 322064231
1 377340243
2 0 363656693
3 316942888
2 2 230204428
1 62852673
2 3 100898827
1 270060377
3 404378154
1 26601435
3 999199607
3 288287628
2 4 11628668
...

output:

result:

ok 199796 lines

Test #42:

score: 0

Accepted

time: 102ms

memory: 19520kb

input:

300000
3 719026031
2 0 243654444
2 0 972110844
3 559390988
2 0 509727974
2 0 913815014
2 0 351407659
2 0 209117912
3 196753993
3 958668852
1 177440170
2 1 125865906
3 498572729
1 775142374
1 611871394
1 526960873
1 46350478
1 66233206
1 366990247
2 1 72605587
1 66540079
2 8 30324354
3 22107932
2 3 1...

output:

0
243654443
972110843
0
509727973
913815013
351407658
209117911
0
0
125865905
0
466154144
30324353
8
257585253
9
9
597411146
10
14
980168901
15
45758131
78652654
492894383
139549410
17
13
241980985
704323336
18
18
20
20
21
159976004
20
20
850494755
214761993
24
24
24
881440093
867854024
24
834676021...

result:

ok 200713 lines

Test #43:

score: 0

Accepted

time: 106ms

memory: 19712kb

input:

300000
2 0 818219322
3 821564513
1 0
2 1 242605730
1 0
1 0
3 787765411
2 1 315911520
2 3 221515123
3 164147396
1 414
3 519640201
3 580756810
2 4 272
1 6297
1 4940
1 7845
3 92940282
2 7 6946
1 1274
1 5492
3 433726347
2 4 388
1 4958
2 4 2
3 966375817
2 9 317
1 9156
1 546
1 8752
3 610978617
2 7 2328
3 ...

output:

result:

ok 199906 lines

Test #44:

score: 0

Accepted

time: 111ms

memory: 21328kb

input:

300000
2 0 40331947
2 0 374648773
3 781316236
2 0 948133808
1 0
3 55546218
1 0
2 1 235718976
1 0
1 0
1 9188
3 158109976
1 5411
1 4006
3 956749419
2 4 634894331
3 885016987
2 1 672915372
3 757373526
2 4 231612982
1 3339
3 497755327
2 6 1617
2 1 596190263
3 439706382
3 624172
2 0 376197223
2 3 3633007...

output:

result:

ok 199858 lines

Test #45:

score: 0

Accepted

time: 57ms

memory: 17332kb

input:

300000
3 647845865
2 0 400216725
2 0 799297587
3 516304862
3 784933302
3 257344997
3 839813569
2 0 167759991
3 788438689
3 15938400
2 0 721185079
2 0 449436686
2 0 666158163
2 0 819220721
3 560050496
2 0 659763128
3 922325401
3 602096973
2 0 884634348
2 0 116610670
2 0 960086525
2 0 429317086
3 1264...

output:

result:

ok 300000 lines

Test #46:

score: -100

Time Limit Exceeded

input:

output: