QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#870998	#9986. Shiori	qnqfff	WA	7ms	11724kb	C++20	2.7kb	2025-01-25 19:03:22	2025-01-25 19:03:24

Judging History

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

[2025-01-25 19:03:24]
评测

测评结果：WA
用时：7ms
内存：11724kb

查看

[2025-01-25 19:03:22]
提交

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=min(read(),100000);for(int i=1;i<=n;i++) a[i]=read(),pos[i]=(i-1)/B+1;
	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;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 9800kb

input:

output:

5
11
22

result:

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

Test #2:

score: 0

Accepted

time: 1ms

memory: 9804kb

input:

1 1
0
1 1 1 0

output:

result:

ok 0 number(s): ""

Test #3:

score: -100

Wrong Answer

time: 7ms

memory: 11724kb

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:

result:

wrong answer Answer contains longer sequence [length = 166844], but output contains 33363 elements