QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #662 | #437405 | #8781. Element-Wise Comparison | chen_zhe_ | C1942huangjiaxu | Failed. | 2024-06-09 10:09:52 | 2024-06-09 10:09:52 |
详细
Extra Test:
Accepted
time: 270ms
memory: 614980kb
input:
50000 4 27032 10928 2532 44626 8762 20413 27349 9539 45885 22452 39755 46650 44687 46933 44001 26820 35258 13391 26027 14764 1766 41604 6438 7463 16164 38009 6816 38517 5922 12241 38416 17843 25153 18347 20417 35606 47761 17474 37782 25357 13437 19367 32389 16713 30838 7607 42643 16950 1162 37080 40...
output:
77542722
result:
ok answer is '77542722'
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #437405 | #8781. Element-Wise Comparison | C1942huangjiaxu | AC ✓ | 391ms | 615260kb | C++14 | 642b | 2024-06-09 10:01:01 | 2024-06-09 10:01:02 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,m,a[N];
bitset<N>b[N],pr[N],su,O;
long long ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
b[a[i]-1].set(i);
}
for(int i=n-1;i;--i)b[i]|=b[i+1];
O.set();
for(int i=1;i<=n;++i)O.reset(i),b[a[i]]&=O;
for(int i=m;i<=n;i+=m){
pr[i]=b[a[i]];
for(int j=1;j<m;++j)pr[i-j]=pr[i-j+1]&(b[a[i-j]]<<j);
ans+=pr[i-m+1].count();
if(i==n)break;
su.set();
for(int j=i-m+2;j<=min(i,n-m+1);++j){
su=(su<<1)&b[a[j+m-1]];
ans+=((pr[j]<<(m-i+j-1))&su).count();
}
}
printf("%lld\n",ans);
return 0;
}