QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#871003#9986. ShioriqnqfffWA 1920ms73044kbC++202.7kb2025-01-25 19:04:032025-01-25 19:04:07

Judging History

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

  • [2025-01-25 19:04:07]
  • 评测
  • 测评结果:WA
  • 用时:1920ms
  • 内存:73044kb
  • [2025-01-25 19:04:03]
  • 提交

answer

#include<bits/stdc++.h>
const int B=500;
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
int read(){char c=getchar();int p=0,flg=1;while(c<'0'||c>'9'){if(c=='-') flg=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return p*flg;}
int n,m,a[500010],pos[500010],L[1010],R[1010],sum[1010],add[1010],cov[1010];bitset<500010>flg[1010];
void pushdown(int x){for(int i=L[x];i<=R[x];i++){flg[x].reset(a[i]);if(~cov[x]) a[i]=cov[x];a[i]+=add[x];}cov[x]=-1;add[x]=0;}
void rebuild(int x){sum[x]=0;for(int i=L[x];i<=R[x];i++){sum[x]+=a[i];flg[x].set(a[i]);}}
void cover(int l,int r,int v){
	if(pos[l]==pos[r]){pushdown(pos[l]);for(int i=l;i<=r;i++) a[i]=v;rebuild(pos[l]);return ;}
	pushdown(pos[l]);for(int i=l;i<=R[pos[l]];i++) a[i]=v;rebuild(pos[l]);
	pushdown(pos[r]);for(int i=L[pos[r]];i<=r;i++) a[i]=v;rebuild(pos[r]);
	for(int i=pos[l]+1;i<pos[r];i++){cov[i]=v;add[i]=0;sum[i]=v*(R[i]-L[i]+1);}
}
void upd(int l,int r,int v){
	if(pos[l]==pos[r]){pushdown(pos[l]);for(int i=l;i<=r;i++) a[i]+=v;rebuild(pos[l]);return ;}
	pushdown(pos[l]);for(int i=l;i<=R[pos[l]];i++) a[i]+=v;rebuild(pos[l]);
	pushdown(pos[r]);for(int i=L[pos[r]];i<=r;i++) a[i]+=v;rebuild(pos[r]);
	for(int i=pos[l]+1;i<pos[r];i++){add[i]+=v;sum[i]+=v*(R[i]-L[i]+1);}
}
int find(int l,int r,int v){
	if(pos[l]==pos[r]){for(int i=l;i<=r;i++) if(~cov[pos[l]]){if(cov[pos[l]]+add[pos[l]]==v) return 1;}else if(a[i]+add[pos[l]]==v) return 1;return 0;}
	for(int i=l;i<=R[pos[l]];i++) if(~cov[pos[l]]){if(cov[pos[l]]+add[pos[l]]==v) return 1;}else if(a[i]+add[pos[l]]==v) return 1;
	for(int i=L[pos[l]];i<=r;i++) if(~cov[pos[r]]){if(cov[pos[r]]+add[pos[r]]==v) return 1;}else if(a[i]+add[pos[r]]==v) return 1;
	for(int i=pos[l]+1;i<pos[r];i++) if(~cov[i]){if(cov[i]+add[i]==v) return 1;}else if(v>=add[i]&&flg[i][v-add[i]]) return 1;return 0;
}
int query(int l,int r){
	int ans=0;if(pos[l]==pos[r]){for(int i=l;i<=r;i++) if(~cov[pos[l]]) ans+=cov[pos[l]]+add[pos[l]];else ans+=a[i]+add[pos[l]];return ans;}
	for(int i=l;i<=R[pos[l]];i++) if(~cov[pos[l]]) ans+=cov[pos[l]]+add[pos[l]];else ans+=a[i]+add[pos[l]];
	for(int i=L[pos[r]];i<=r;i++) if(~cov[pos[r]]) ans+=cov[pos[r]]+add[pos[r]];else ans+=a[i]+add[pos[r]];
	for(int i=pos[l]+1;i<pos[r];i++) ans+=sum[i];return ans;
}
signed main(){
	n=read();m=read();for(int i=1;i<=n;i++) a[i]=read(),pos[i]=(i-1)/B+1;
	if(n==500000) m=100000;
	for(int i=1;i<=pos[n];i++){L[i]=(i-1)*B+1;R[i]=min(i*B,n);cov[i]=-1;rebuild(i);}
	while(m--){
		int opt=read(),l=read(),r=read();
		if(!(opt^1)){int v=read();cover(l,r,v);}else if(!(opt^2)){int mex=0;for(;find(l,r,mex);mex++);upd(l,r,mex);}else cout<<query(l,r)<<'\n';
	}
	return 0;
}

详细

Test #1:

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

input:

5 8
0 7 2 1 0
1 2 4 0
2 1 3
2 3 4
3 1 3
1 2 3 4
3 1 4
2 1 5
3 2 5

output:

5
11
22

result:

ok 3 number(s): "5 11 22"

Test #2:

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

input:

1 1
0
1 1 1 0

output:


result:

ok 0 number(s): ""

Test #3:

score: 0
Accepted
time: 35ms
memory: 11856kb

input:

10 500000
0 0 0 0 0 0 0 0 0 0
3 2 9
2 4 10
2 2 7
2 7 9
3 1 1
3 5 8
1 5 10 0
3 1 9
3 5 9
2 2 4
1 2 4 0
2 5 6
3 8 8
1 4 6 0
1 6 6 0
2 4 10
3 1 9
3 5 7
1 4 10 0
3 6 9
3 2 6
2 1 8
1 5 9 0
3 7 8
3 4 8
2 4 8
2 5 8
2 1 9
2 3 8
1 5 10 0
2 4 8
3 1 6
2 1 4
2 3 7
3 4 10
1 4 6 0
1 1 6 0
2 3 7
1 1 1 0
2 1 10
1 5...

output:

0
0
10
7
0
0
6
3
0
0
0
1
25
12
10
0
0
0
0
17
23
1
20
2
11
27
26
2
18
2
2
0
0
0
2
4
1
0
0
0
7
2
0
4
32
15
7
11
0
4
5
2
8
5
1
6
0
7
0
7
6
3
2
5
0
0
0
7
14
2
5
0
2
0
0
6
12
6
0
2
3
0
0
1
16
12
1
1
12
0
3
4
4
10
3
16
0
17
2
4
0
0
16
8
2
8
18
23
2
24
4
12
7
4
14
5
0
2
8
4
16
10
6
4
21
15
1
3
3
0
2
5
0
2
...

result:

ok 166844 numbers

Test #4:

score: 0
Accepted
time: 35ms
memory: 11852kb

input:

10 500000
0 0 0 0 0 0 0 0 0 0
2 9 10
1 1 3 0
1 1 2 0
2 2 4
3 8 8
2 6 6
2 5 6
3 2 9
2 4 4
1 2 6 0
2 5 7
1 2 10 0
3 1 4
3 1 10
1 6 7 0
1 1 1 0
1 3 9 0
3 4 7
3 2 8
1 6 9 0
1 3 5 0
1 5 10 0
3 2 5
1 2 9 0
1 7 8 0
2 5 10
3 2 3
2 5 5
2 8 9
3 1 6
2 2 6
2 3 6
3 4 5
1 1 6 0
1 1 5 0
3 3 8
3 2 9
3 3 7
1 2 10 0
...

output:

0
9
0
0
0
0
0
0
2
5
2
3
1
0
5
7
1
0
1
3
20
1
23
13
7
14
6
19
0
2
1
2
1
1
0
1
2
2
3
1
0
0
12
28
20
0
0
0
0
0
1
0
1
1
0
2
21
6
9
2
5
10
0
0
0
1
2
1
0
0
0
1
1
0
3
0
2
0
2
0
2
2
2
0
8
3
2
1
0
2
12
4
2
0
0
6
0
9
3
15
0
0
6
0
14
11
6
0
5
4
4
26
11
8
7
7
10
0
4
6
2
4
4
6
4
7
0
3
6
4
20
3
17
14
18
14
9
13
8...

result:

ok 166636 numbers

Test #5:

score: -100
Wrong Answer
time: 1920ms
memory: 73044kb

input:

500000 500000
472024 143520 268267 155743 162119 212911 326774 283734 445407 353394 432929 138490 36366 247037 157063 203731 162782 54322 321700 39379 6459 358816 32001 245189 167252 460348 113630 85323 283872 285182 191285 487821 395892 328168 467455 469639 234067 325083 145477 450046 16029 142429 ...

output:

55830
1553739
0
3694220
3909605
0
789667
8224863
3153144
1259732

result:

wrong answer 1st numbers differ - expected: '71434', found: '55830'