fork download
copy 
  1. #include <vector>
  2. #include <map>
  3. #include <set>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <cstring>
  9. #include <cassert>
  10. #include <queue>
  11. using namespace std;
  12. #define forr(i, a, b) for(ll i = (a); i < (ll) (b); i++)
  13. #define forn(i, n) forr(i, 0, n)
  14. #define pb push_back
  15. #define fst first
  16. #define snd second
  17. #define SZ(x) ((ll)x.size())
  18. typedef long long ll;
  19. #define dforn(i, n) for(ll i = n - 1; i >= 0; i--)
  20.  
  21. const ll MAXN = 200200;
  22. const ll INF = (ll)1e18;
  23.  
  24. ll n,k,A[MAXN],B[MAXN],bn,real[MAXN],L[MAXN],R[MAXN];
  25. ll add[MAXN];
  26.  
  27. bool OF(ll a, ll b){
  28.   return a > (INF+b-1)/b;
  29. }
  30.  
  31. int main() {
  32.   //~ freopen("input.in", "r", stdin);
  33.   while( scanf("%lld%lld", &n,&k) >= 1 ){
  34.     ll ans=0;bn=0;add[0]=0;
  35.     forn(i,n){
  36.       scanf("%lld",&A[i]);
  37.       add[i+1]=add[i]+A[i];
  38.     }
  39.     ll cnt=0;
  40.     forn(i,n){
  41.       if(A[i]>1){
  42.         B[bn]=A[i];
  43.         L[bn]=cnt;
  44.         real[bn]=i;
  45.         bn++;
  46.         cnt=0;
  47.       } else {
  48.         if(k==1)ans++;
  49.         cnt++;
  50.       }
  51.     }
  52.     cnt=0;
  53.     ll pnt=bn-1;
  54.     dforn(i,n){
  55.       if(A[i]>1){
  56.         R[pnt--]=cnt;
  57.         cnt=0;
  58.       } else {
  59.         cnt++;
  60.       }
  61.     }
  62.     //~ printf("bn=%lld\n",bn);
  63.     forn(i,bn){
  64.       ll p=1LL;
  65.       forr(j,i,bn){
  66.         if(OF(p,B[j]))break;
  67.         p*=B[j];
  68.         if(p%k)continue;
  69.         ll s = add[real[j]+1]-add[real[i]];
  70.         ll t=p/k-s;
  71.         //~ printf("[%lld,%lld] = %lld, p=%lld,t=%lld\n",i,j,s,p,t);
  72.         if(t<0)continue;
  73.         if(t==0){
  74.           ans++;
  75.           continue;
  76.         }
  77.         ll LL=L[i];
  78.         ll RR=R[j];
  79.         if(LL+RR<t)continue;
  80.         ll mm=min(LL,RR);
  81.         ll MM=max(LL,RR);
  82.         //~ printf("so far mm=%lld, MM=%lld\n",mm,MM);
  83.         mm=min(t,mm);
  84.         MM=min(t,MM);
  85.         ans+=min(mm+1,MM-(t-mm)+1);
  86.         //~ if(mm==t)ans++;
  87.         //~ if(MM==t)ans++;
  88.         //~ printf("Entre %lld y %lld, p=%lld, s=%lld, mm=%lld, MM=%lld t=%lld\n",i,j,p,s,mm,MM,t);
  89.       }
  90.     }
  91.     printf("%lld\n",ans);
  92.   }
  93.   return 0;
  94. }
Success #stdin #stdout 0s 4260KB
comments (?)
stdin
copy 
10 2 
1 1 1 1 10 3 1 1 1 1
stdout
copy 
3
https://ideone.com/CHh3Yb
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!