QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114771#5022. 【模板】线段树lgvc#25 1239ms168144kbC++232.1kb2023-06-23 15:55:132024-05-31 14:10:47

Judging History

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

  • [2024-05-31 14:10:47]
  • 评测
  • 测评结果:25
  • 用时:1239ms
  • 内存:168144kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-23 15:55:13]
  • 提交

answer

//这回只花了114514min就打完了。
//真好。记得多手造几组。
#include <bits/stdc++.h>
//#define int long long
#define pai 3.141592653589793238462643383279502884197169399375105820
#define MOD 1000000007
#define eps 0.00000001
inline int min(int a,int b) {return a<b?a:b;}
inline int max(int a,int b) {return a>b?a:b;}
#define ULL unsigned long long
#define LL long long
#define INF 0x3f3f3f3f
#define INF_LL 0x3f3f3f3f3f3f3f3f
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
	if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
	*pp++=ch;
}
inline void pcc(){
	fwrite(buf2,1,pp-buf2,stdout);
	pp=buf2;
}
inline int read(void) {
	register int x(0);register char c(getchar());
	while(c<'0'||c>'9') {c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}
void write(int x) {
	static int sta[20];
	int top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while(x);
	while(top) pc(sta[--top]+48);
}
void we(int x) {
	write(x);
	pc('\n');
}
inline bool cmp_xi(int a,int b) {return a<b;}
inline bool cmp_da(int a,int b) {return a>b;}
int T,N,Q,ct,st[250009],a[250009];
std::unordered_map<LL,int> vi;
int f(int x,int y) {
	if(x==0) return a[y];
	int m=vi[1ll*x*N+y]; 
	if(m) return m-1;
	int as=f(x-(1<<st[x]),y);
	if(y>(1<<st[x])) as^=f(x-(1<<st[x]),y-(1<<st[x]));
	vi[1ll*x*N+y]=as+1;
	return as;
}
signed main(void) {
   // freopen("m.in","r",stdin);
   // freopen("m.out","w",stdout);
    T=read();N=read();Q=read();
    assert(T==4||T==5||T==6);
    for(int i=1;i<=Q;i++) {
    	for(int j=19;j>=0;j--) {
    		if((i>>j)&1) {
    			st[i]=j;
    			break;
			}
		}
	}
    for(int i=1;i<=N;i++) {
    	a[i]=read(); 
	} 
	while(Q--) {
		int op=read();
		if(op==1) {
			int l=read(),r=read();
			ct++;
		} else {
			int x=read();
			we(f(ct,x));
		}
	}
	for(int i=0;i<=19;i++) {
		if((ct>>i)&1) {
			for(int j=N;j>(1<<i);j--) {
				a[j]^=a[j-(1<<i)];
			}
		}
	}
	for(int i=1;i<=N;i++) we(a[i]);
	pcc();
    return 0;
}


详细

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

1
6 6
1 1 5 1 9 4
2 5
1 2 5
2 4
1 3 6
2 6
1 1 6

output:


result:


Subtask #2:

score: 0
Runtime Error

Test #6:

score: 0
Runtime Error

input:

2
249998 99999
1048488450 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #10:

score: 0
Runtime Error

input:

3
250000 99999
1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1...

output:


result:


Subtask #4:

score: 13
Accepted

Test #14:

score: 13
Accepted
time: 743ms
memory: 97476kb

input:

4
249996 99997
309331355 195839266 912372930 57974187 363345291 954954162 650621300 389049294 821214285 263720748 231045308 844370953 768579771 664766522 681320982 124177317 32442094 297873605 743179832 1073656106 443742270 235746807 1054294813 974443618 422427461 307448375 1018255356 20105813 36821...

output:

611117059
866091251
300188933
0
478915924
1053588351
453142424
897441996
60971719
748656483
600408393
0
303761852
983037069
883016404
332332552
1069626159
860304528
851235295
561276840
389049294
681320982
484263000
351914192
620106464
667080579
733146026
375466744
0
347632358
737240082
321494160
0
3...

result:

ok 299980 numbers

Test #15:

score: 0
Accepted
time: 307ms
memory: 58384kb

input:

4
249996 99997
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
707358968
0
0
0
165359261
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
301087804
0
0
0
0
...

result:

ok 348991 numbers

Test #16:

score: 0
Accepted
time: 33ms
memory: 16188kb

input:

4
249996 100000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

0
0
0
0
0
0
0
0
412012733
460047966
0
0
0
94984489
0
0
0
0
1010860949
0
0
0
336953687
0
0
0
0
0
655564155
25780913
662736870
0
0
0
0
0
679917886
0
998313118
0
0
0
0
0
171168202
20014081
336953687
0
0
0
0
1018313742
0
997397452
0
849015355
0
16108473
0
0
0
504340154
0
397006673
0
0
0
0
0
0
290851883
...

result:

ok 250950 numbers

Test #17:

score: 0
Accepted
time: 849ms
memory: 107500kb

input:

4
249999 99998
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
956381802
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1021925694
922314342
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 300062 numbers

Subtask #5:

score: 12
Accepted

Test #18:

score: 12
Accepted
time: 13ms
memory: 7436kb

input:

5
249997 99997
860563869 428592873 58576739 761578583 47999879 294581118 988847649 569566599 640106250 440172702 178219106 966598261 763325707 846927552 877923116 145156535 246778542 25949847 507939778 116507169 555239769 259969305 328955819 171606729 535970481 121608060 4437163 370976515 713807003 ...

output:

860563869
717285236
452329866
773393204
485721677
965902221
831024341
890990738
455498944
92913689
556500009
102303365
264515518
445496274
654612933
988537886
165104807
364103659
952755344
576499197
775866335
1003839403
606880290
1006459039
1005979559
588810854
592470517
765610807
123827263
86327854...

result:

ok 249997 numbers

Test #19:

score: 0
Accepted
time: 13ms
memory: 7152kb

input:

5
249998 100000
1055401468 532211763 131695513 214363867 831955115 452049333 729606869 69161863 428100767 90941242 729034740 90774107 332674212 930394013 601735907 104187221 1017052616 31513597 868964816 1054507185 926990168 75998133 1039482150 781325037 680316641 471310435 780674964 330142918 10271...

output:

1055401468
532211763
131695513
214363867
831955115
452049333
729606869
69161863
428100767
90941242
729034740
90774107
332674212
930394013
601735907
104187221
1017052616
31513597
868964816
1054507185
926990168
75998133
1039482150
781325037
680316641
471310435
780674964
330142918
1027184688
750941669
...

result:

ok 249998 numbers

Test #20:

score: 0
Accepted
time: 14ms
memory: 7424kb

input:

5
249999 65535
206222027 1038492265 248834236 84032585 981309757 273118313 589015947 1002433231 482381717 342803573 48417408 196676553 50772773 199061806 637191822 974252922 289297532 48985206 415073252 593023329 9193325 632026989 55397875 918843456 476033799 664362612 383124333 926156312 133237149 ...

output:

206222027
833392802
1064859678
981091415
515434
272673027
861602440
149219399
337930194
4891559
44591399
152134382
169335243
30058725
607153771
505513233
253743469
234136859
357115647
907147166
916304115
322324382
276499053
650082861
987810090
494507870
196056115
1016828459
996842422
602075803
53081...

result:

ok 249999 numbers

Subtask #6:

score: 0
Time Limit Exceeded

Dependency #5:

100%
Accepted

Test #21:

score: 16
Accepted
time: 942ms
memory: 111544kb

input:

6
249999 99998
234899190 294042590 622374272 592723113 719234312 350081074 842293736 684699037 330659123 145765638 707972395 212219898 665588169 1002656251 377046330 569400576 515159132 246671859 367313733 436193585 1056439739 889727758 441186237 802117710 672761337 1013893805 760105556 959623512 10...

output:

416342969
682608684
897388094
564167584
723521403
277032360
571217154
804968920
345689708
20430886
2669323
397914023
682539746
743678615
902811241
79705781
117866215
29290630
463835109
948618157
996425135
333840809
879030503
756069154
651860206
62844241
563208222
473841643
306068071
945671265
755499...

result:

ok 340922 numbers

Test #22:

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

input:

6
249999 100000
440794180 373448998 924631752 1029747555 1025197824 772227211 39885098 362601933 28836613 109487897 1065155159 170512808 1054469991 504110707 412993411 172546234 861597564 320825471 551313957 607675657 108258007 713412450 183442416 266654936 968422736 230720896 824830683 653610670 10...

output:

98475211
195528780
696822840
514087003
829956911
329558613
774154603
206369270
459595700
862203687
923064620
893978487
446169540
162819606
623685563
362210402
266466497
536712664
619196444
636251427
621982108
29822991
825999568
1023819390
976493671
1002043855
522408337
819431256
487829199
839724281
...

result:

ok 258991 numbers

Test #23:

score: 0
Accepted
time: 1239ms
memory: 168144kb

input:

6
249997 99996
858874420 647336645 792849435 487078011 572740439 880018128 888095353 792485726 562377029 925278515 769802546 863097170 1024187886 86325040 278572503 296068408 305389187 156383560 564344122 985485618 352643959 100128572 51313514 939087520 196935800 175799309 561623994 704660004 265677...

output:

432854594
738728738
262426424
538231132
618966731
444275244
553066863
973600567
229016163
137911233
474170208
151027732
489894673
52703384
860246793
29393762
677235209
677602352
528898618
55456646
169243833
468519972
485795189
732890985
359625381
702665297
407151543
225249034
52286602
259376944
8254...

result:

ok 316451 numbers

Test #24:

score: -16
Time Limit Exceeded

input:

6
249996 99998
397969543 991721013 639702540 604481296 351426688 333740122 724850461 729736402 79245133 118976945 532880690 120525599 614643743 490724539 699303708 215416342 87908710 952073016 139568877 646769946 252759252 177392171 163619316 265404108 1038973785 470689235 333983939 483290379 506253...

output:


result:


Subtask #7:

score: 0
Runtime Error

Dependency #5:

100%
Accepted

Test #28:

score: 0
Runtime Error

input:

7
249999 99998
1028875149 290751586 85260062 527433830 11253389 381520904 163374626 882045937 328797576 362761070 107207247 721987314 848366187 492948114 913994419 980121735 553555299 238308272 517289115 493658637 535863518 18389830 59694996 328276770 970756488 409396240 782649706 568544673 92874299...

output:


result:


Subtask #8:

score: 0
Skipped

Dependency #1:

0%