QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114804#5022. 【模板】线段树lgvc#8 2342ms7144kbC++232.4kb2023-06-23 16:47:102024-05-31 14:10:56

Judging History

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

  • [2024-05-31 14:10:56]
  • 评测
  • 测评结果:8
  • 用时:2342ms
  • 内存:7144kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-23 16:47:10]
  • 提交

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;
}
void fc(void) {
    for(int i=1;i<=Q;i++) {
    	for(int j=19;j>=0;j--) {
    		if((i>>j)&1) {
    			st[i]=j;
    			break;
			}
		}
	}
	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();	
}
signed main(void) {
   // freopen("m.in","r",stdin);
   // freopen("m.out","w",stdout);
    T=read();N=read();Q=read();
    if(T==4||T==5||T==6) {
    	fc();
    	return 0;
	}
	for(int i=1;i<=N;i++) {
    	a[i]=read(); 
	}
	while(Q--) {
		int op=read();
		if(op==1) {
			int l=read(),r=read();
			for(int i=r;i>l;i--) a[i]^=a[i-1];
		} else {
			int x=read();
			we(a[x]);
		}
	} 
	for(int i=1;i<=N;i++) we(a[i]);
	pcc();		
    return 0;
}


详细

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 0ms
memory: 5616kb

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:

9
4
12
1
0
5
4
12
0

result:

ok 9 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 5808kb

input:

1
999 997
898798734 979577086 45974352 1013270193 1053191143 533594258 372426673 947830633 122319874 368651315 866424479 109724831 427664962 558099346 764830489 326451620 322471751 525780385 746941281 670254345 586958579 979544209 743892216 436404384 291681381 979530194 998929567 367716728 909076993...

output:

1015342581
962986689
965094083
871356796
835210392
172023195
63088572
606096781
569607283
436055720
154605892
663158209
154605892
776365236
281312240
62398687
182713417
604764772
816533315
793514230
325061861
806973284
91749226
283750235
198953311
170342298
432592070
809908556
683302450
40932811
669...

result:

ok 1996 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 5588kb

input:

1
999 997
89872218 906651903 120274311 490547919 291584020 755757065 24942887 707247173 763024744 68250332 114193028 999245166 140381610 171802205 399965713 299821903 907998064 906075056 427270276 335420206 708713870 492555323 359637714 197212814 35225369 1011322274 912003632 633998134 1026276199 85...

output:

89872218
860962725
120274311
490547919
978745892
924706625
610771729
524956121
105748312
139294727
866385688
729638611
92178006
1037482711
80194776
277477501
592738191
694314356
733017733
701758468
65199929
983529101
717179143
542164040
444291361
439952700
147939819
276321083
1012586084
166061298
30...

result:

ok 999 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

1
998 997
802301789 913975794 256883306 462593698 958614999 708264636 114045898 622336472 273146091 1035403087 151608039 853195969 670449389 1967248 347890740 88419426 272759411 668812195 315110503 54515201 11283025 183682542 149656693 916299553 345162140 626592021 633508243 201443721 191882154 4200...

output:

654798390
720797824
232736065
90537128
467468783
391542471
410387328
970043816
199400953
691327788
183682542
543340459
435746483
305146388
967107550
72899382
419833683
273367829
1062016570
511549763
893866015
137019003
177123936
524992882
462306449
1057090504
72525968
344810664
332588248
94524245
57...

result:

ok 1491 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

1
10 64
178 181 183 184 188 189 190 191 192 195
1 3 5
2 10
2 8
1 4 9
2 10
2 2
1 1 5
2 5
2 3
2 3
1 2 7
2 3
1 3 9
2 7
1 1 8
1 2 8
2 7
2 7
2 5
2 2
2 7
2 5
1 2 7
1 8 10
1 2 3
1 6 10
1 5 6
1 5 7
2 4
1 5 10
1 2 5
2 3
1 4 7
2 5
1 2 10
1 3 10
1 2 5
2 3
1 1 3
1 2 7
2 10
1 2 9
2 4
1 2 6
2 10
1 4 6
1 2 9
2 4
2...

output:

195
191
195
181
4
2
2
5
7
1
1
3
181
1
3
15
2
12
2
6
189
6
186
7
9
6
125
13
13
189
189
183
178
181
183
10
4
14
189
179
122
6

result:

ok 42 numbers

Subtask #2:

score: 0
Time Limit Exceeded

Test #6:

score: 4
Accepted
time: 2342ms
memory: 6664kb

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:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 300080 numbers

Test #7:

score: -4
Time Limit Exceeded

input:

2
249999 100000
734489692 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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
Time Limit Exceeded

Test #10:

score: 7
Accepted
time: 1725ms
memory: 7144kb

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:

0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
1
1
0
1
1
0
1
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
0
0
0
1
1
1
0
1
1
0
0
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
1
0
0
0
1
1
0
0
0
1
1
1
0
1
1
1
1
1
0
1
0
1
1
0
1
1
1
0
0
1
1
1
0
0
0
1
0
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
0
...

result:

ok 300215 numbers

Test #11:

score: -7
Time Limit Exceeded

input:

3
249996 100000
1 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 ...

output:


result:


Subtask #4:

score: 0
Runtime Error

Test #14:

score: 0
Runtime Error

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:


result:


Subtask #5:

score: 0
Runtime Error

Test #18:

score: 0
Runtime Error

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:


result:


Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #5:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%