|

General

# Author Problem Lang Verdict Time Memory Sent Judged
137278523 Practice:
hawai_chappal
1609C - 48 GNU C++17 Accepted 93 ms 9776 KB 2021-11-28 22:54:14 2021-11-28 22:54:14
→ Source
#include <bits/stdc++.h>
using namespace std;

#define begin_code_from_here ios_base::sync_with_stdio(false); cin.tie(NULL);

bool prime[1000000+1];

void Sieve()
{
long long n = 1000000;
memset(prime, true, sizeof(prime));

for (long long p = 2; p * p <= n; p++)
{
if (prime[p] == true)
{
for (long long i = p * p; i <= n; i += p)
prime[i] = false;
}
}

}

int main(){
begin_code_from_here

Sieve();
long long t;
cin >> t;
while(t--){
long long n,e;
cin >> n >> e;
vector<long long> a(n+1);
for(long long i = 1 ; i <=n ; i++) cin >> a[i];
vector<vector<long long>> dp(n+1,vector<long long>(2));
//dp[n+1] = {-1,-1};
/*
DP state : { index of prime no. > 1, last index of one}
*/

for(long long i = n ; i >= 1 ; i--){
if(prime[a[i]]){
if(a[i] > 1){
if(i+e <= n){
if(!prime[a[i+e]]){
dp[i] = dp[i+e];
dp[i][0] = i;
continue;
}
auto last_state = dp[i+e];
if(last_state[0] != -1){
// we already have a prime num in this streal
dp[i][0] = i;
dp[i][1] = dp[i+e][0] - e;
if(dp[i][1] == i){
dp[i][1] = -1;
}
}
else{
dp[i][1] = dp[i+e][1];
dp[i][0] = i;
}
}
else{
dp[i][0] = i;
dp[i][1] = -1;
}
}
else{
if(i+e <= n){
if(!prime[a[i+e]]){
dp[i] = dp[i+e];
dp[i][1] = i;
continue;
}
dp[i][0] = dp[i+e][0];
dp[i][1] = dp[i+e][1];
}
else {
dp[i][0] = -1;
dp[i][1] = i;
}
}
}
else{
dp[i] = {-1,-1};
}
}

long long ans = 0;
for(long long i = 1 ; i <= n ;i++){
if(prime[a[i]]){
if((dp[i][0] == -1 && a[i] == 1) || (dp[i][0] == -1 && dp[i][1] == -1)){
continue;
}
else{
long long mx_pos=i;
if(a[i] == 1){
if(dp[i][1] < dp[i][0]){
ans++;
}
else{
ans += (dp[i][1] - dp[i][0])/e + 1;
}
}
else{
mx_pos = max(mx_pos,dp[i][0]);
mx_pos = max(mx_pos,dp[i][1]);
ans += (mx_pos-i) / e;
}
}
}
}
cout << ans << "\n";
}

return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?