QOJ.ac
QOJ
| ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
|---|---|---|---|---|---|---|---|
| #669 | #437405 | #8781. Element-Wise Comparison | chen_zhe_ | C1942huangjiaxu | Failed. | 2024-06-09 10:13:31 | 2024-06-09 10:13:32 |
Details
Extra Test:
Accepted
time: 361ms
memory: 615060kb
input:
50000 140 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 ...
output:
0
result:
ok answer is '0'
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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;
}