fork(5) download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. #include<deque>
  5. #include<algorithm>
  6. #include<cmath>
  7. #include<set>
  8. #include<map>
  9. #include<cstdio>
  10. using namespace std;
  11. #define int long long
  12. #define inf 1000000000000000001
  13. #define mn 300005
  14. #define FLN "test"
  15.  
  16. int n, A[mn], k;
  17. int Pfx[mn]; // Prefix Sum
  18. int Prv[mn]; // Prv[i] is the position right after the nearest 'good' number
  19.  
  20. main()
  21. {
  22. 	ios_base::sync_with_stdio(false);
  23. 	cin.tie(0);
  24. 	cout.tie(0);
  25.  
  26. 	Pfx[0]=0;
  27. 	cin>>n>>k;
  28. 	for (int i=1; i<=n; i++) 
  29. 	{
  30. 		cin>>A[i];
  31. 		Pfx[i]=Pfx[i-1]+A[i];
  32. 	}
  33. 	int ptr=0;
  34. 	for (int i=1; i<=n; i++)
  35. 	{
  36. 		Prv[i]=ptr+1;
  37. 		if (A[i]>1) ptr=i;
  38. 	}
  39.  
  40.  
  41. 	int ans=0;
  42. 	for (int i=1; i<=n; i++)
  43. 	{
  44. 		int curprd=1; // current product
  45.  
  46. 		int ptr=i;
  47. 		while (ptr>0)
  48. 		{
  49. 			if (inf/A[ptr]<=curprd) break; // Compare these instead of multiplying reduce the risk of overflowing
  50. 			curprd*=A[ptr];
  51.  
  52. 			int l=(Pfx[i]-Pfx[ptr-1])*k; //pos of the current 'good' number
  53.  
  54. 			ptr=Prv[ptr];
  55. 			if (ptr<=0) break;
  56. 			int r=(Pfx[i]-Pfx[ptr-1])*k; //pos of the next 'good' number plus one
  57. 			if (curprd%k==0 && curprd>=l && curprd<=r) ans++; //find out if there are any solution between the 1's
  58. 			ptr--;
  59. 		}
  60. 	}
  61.  
  62. 	cout<<ans;
  63. }
  64.  
  65. // PLEASE REMOVE COUT DEBUG, FILE-OPENING FUNCTIONS BEFORE SUBMITTING
  66. // Code by low_ 
  67. // Link: http://c...content-available-to-author-only...s.com/contest/992/problem/D
Success #stdin #stdout 0s 4428KB
comments (?)
stdin
copy 
4 2
6 3 8 1
stdout
copy 
2
https://ideone.com/JLNwsZ
language:
C++14 (gcc 8.3)
created:
5 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!