QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#439918#8781. Element-Wise Comparisonas_lyrWA 240ms938768kbC++141011b2024-06-12 20:36:242024-06-12 20:36:25

Judging History

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

  • [2024-06-12 20:36:25]
  • 评测
  • 测评结果:WA
  • 用时:240ms
  • 内存:938768kb
  • [2024-06-12 20:36:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=51000;
int n,m;
int a[N];
pair <int,int> p[N];
bitset <N> b[N];
int tp[N],lx[N],rx[N];
bitset <N> l[N],r[N];
bitset <N> bt; 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		p[i]=make_pair(a[i],i);
	}
	sort(p+1,p+n+1,[](const pair <int,int> x,const pair <int,int> y){
		return x.first<y.first;
	});
	for(int i=1;i<=n;i++){
		b[p[i].second]=b[p[i-1].second];
		b[p[i].second][p[i-1].second]=1;
	}
	for(int i=1;i<=n;i++)
		tp[i]=(i-1)/m+1;
	for(int i=n;i;i--)
		lx[tp[i]]=i;
	for(int i=1;i<=n;i++)
		rx[tp[i]]=i;
	for(int i=1;i<=tp[n];i++){
		l[lx[i]]=b[lx[i]];
		for(int j=lx[i]+1;j<=rx[i];j++)
			l[j]=l[j-1]&b[j];
		r[rx[i]]=b[rx[i]];
		for(int j=rx[i]-1;j>=lx[i];j--)
			r[j]=r[j+1]&b[j];
	}
	int ans=0;
	for(int i=1;i+m-1<=n;i++){
		if(i==lx[i])
			ans+=(int)(r[i]&bt).count();
		else
			ans+=(int)(r[i]&r[i+m-1]&bt).count();
		bt[i]=1;
	}
	printf("%d",ans);
	return 0;
}

详细

Test #1:

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

input:

5 3
5 2 1 3 4

output:

0

result:

ok answer is '0'

Test #2:

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

input:

5 2
3 1 4 2 5

output:

2

result:

ok answer is '2'

Test #3:

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

input:

4 2
1 2 3 4

output:

3

result:

ok answer is '3'

Test #4:

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

input:

4 2
4 3 2 1

output:

0

result:

ok answer is '0'

Test #5:

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

input:

1 1
1

output:

0

result:

ok answer is '0'

Test #6:

score: -100
Wrong Answer
time: 240ms
memory: 938768kb

input:

50000 2
44045 29783 5389 7756 44022 45140 21967 5478 10868 49226 21775 31669 49836 13511 46116 14229 27206 31168 37389 3158 10658 41154 14635 18526 40540 6451 23197 46719 30593 13517 8604 46666 39189 43746 12778 3684 3194 36979 43020 14652 19549 31178 17144 27177 44336 2849 40220 11751 41993 32209 4...

output:

363943937

result:

wrong answer expected '310780127', found '363943937'