fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Numeric Constants
  5. #define N 1000000007
  6. #define maxs 300005
  7. #define mins 1005
  8. #define eps 0.000000000001
  9. #define imax 2000000200
  10. #define llmax 1000000002000000000ll
  11. #define pi 3.141592653589793
  12.  
  13. // Others
  14. #define ll long long
  15. #define pb push_back
  16. #define gc getchar_unlocked
  17. #define iosbase ios_base::sync_with_stdio(false)
  18. #define pii pair<int,int>
  19. #define pll pair<ll,ll>
  20. #define ppi pair<pair<int,int>,int>
  21. #define ppl pair<pll,ll>
  22. #define vi vector<int>
  23. #define sc scanf
  24. #define pr printf
  25. #define lld I64d
  26. #define F first
  27. #define S second
  28. #define siter set<int>::iterator
  29. #define p_pq priority_queue
  30. #define ub upper_bound
  31. #define lb lower_bound
  32.  
  33. int z[maxs],dp[maxs],given[maxs],search1[maxs],search2[maxs];
  34. vector<int>v;
  35. void calcZ(vector<int>s){
  36. 	int l=0,r=0;
  37. 	int n=s.size();
  38. 	for(int i=1;i<n;i++){
  39. 		if(i>r){
  40. 			l=r=i;
  41. 			while(r<n && s[r-l]==s[r]){
  42. 				r++;
  43. 			}
  44. 			z[i]=r-l;
  45. 			r--;
  46. 		}
  47. 		else{
  48. 			int k=i-l;
  49. 			if(z[k]<r-i+1){
  50. 				z[i]=z[k];
  51. 			}
  52. 			else{
  53. 				l=i;
  54. 				while(r<n && s[r-l]==s[r]){
  55. 					r++;
  56. 				}
  57. 				z[i]=r-l;
  58. 				r--;
  59. 			}
  60. 		}
  61. 	}
  62. }
  63. int main()
  64. {
  65. 	int n,k,l,i,j;
  66. 	sc("%d %d %d",&n,&k,&l);
  67. 	for(i=0;i<n;i++){
  68. 		sc("%d",&given[i]);
  69. 	}
  70. 	for(i=0;i<k;i++){
  71. 		sc("%d",&search1[i]);
  72. 	}
  73. 	for(i=0;i<l;i++){
  74. 		sc("%d",&search2[i]);
  75. 	}
  76. 	for(i=0;i<k;i++){
  77. 		v.pb(search1[i]);
  78. 	}
  79. 	v.pb(-1);
  80. 	for(i=0;i<n;i++){
  81. 		v.pb(given[i]);
  82. 	}
  83. 	calcZ(v);
  84. 	for(i=0;i<n;i++){
  85. 		if(z[i+k+1]==k){
  86. 			dp[i]=1;
  87. 		}
  88. 	}
  89. 	for(i=n-1;i>=0;i--){
  90. 		dp[i]=dp[i]+dp[i+1];
  91. 	}
  92. 	v.clear();
  93. 	for(i=0;i<l;i++){
  94. 		v.pb(search2[i]);
  95. 	}
  96. 	v.pb(-1);
  97. 	for(i=0;i<n;i++){
  98. 		v.pb(given[i]);
  99. 	}
  100. 	calcZ(v);
  101. 	ll ans=0;
  102. 	for(i=0;i<n;i++){
  103. 		if(z[i+l+1]==l){
  104. 			ans+=dp[i];
  105. 		}
  106. 	}
  107. 	pr("%lld\n",ans);
  108. 	return 0;
  109. }
Time limit exceeded #stdin #stdout 5s 9320KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HswpMn
language:
C++14 (gcc 8.3)
created:
9 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!