fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define MAX 50001
  4. #define EPS 1e-9
  5. #define MOD 1000000007
  6. #define INF 1e9
  7. #define pn() printf("\n")
  8. #define vint vector <int>
  9. #define vpint vector <pair<int,int> >
  10. #define pb push_back
  11. #define mp make_pair
  12. #define ft first
  13. #define sd second
  14. #define gc() getchar_unlocked()
  15. #define ms(x,v) memset(x,v,sizeof x)
  16. #define pr_arr(i,x,size) for(i=0;i<size;i++) cout<<x[i]<<" "
  17. #define ff(i,a,b) for(i=a;i<=b;i++)
  18. #define fb(i,a,b) for(i=a;i>=b;i--)
  19. #define gprint(i) cout<<"Case #"<<i<<": "
  20. using namespace std;
  21.  
  22. bool fib[100000];
  23. int P[100000];
  24. vint v;
  25.  
  26. void find_fib()
  27. {
  28. 	fib[0]=1;
  29. 	fib[1]=1;
  30. 	int f=0,s=1,n,i;
  31. 	for(int c=0;s<MAX;c++)
  32.   	{
  33.       	if(c<=1)
  34.       		n=c;
  35.       	else
  36.       	{
  37.         	n=f+s;
  38.         	f=s;
  39.         	s=n;
  40.       	}
  41.       	fib[s]=true;
  42.    	}
  43. }
  44.  
  45. void calc()
  46. {
  47. 	P[0]=0;
  48. 	P[1]=1;
  49. 	v.pb(1);
  50. 	int i,j;
  51. 	for(i=2;i<MAX;i++)
  52. 	{
  53. 		if(fib[i])
  54. 		{
  55. 			P[i]=1;
  56. 			v.pb(i);
  57. 			continue;
  58. 		}
  59. 		else
  60. 		{
  61. 			int mini=INT_MAX;
  62. 			for(j=0;j<v.size() && i-v[j]>0;j++)
  63. 			{
  64. 				mini=min(mini,P[i-v[j]]+1);
  65. 			}
  66. 			P[i]=mini;
  67. 		}
  68. 	}
  69. }
  70.  
  71. int main()
  72. {
  73.     //ios::sync_with_stdio(false);
  74.     find_fib();
  75.     calc();
  76.     int n,k,m,q,i;
  77.     cin>>n>>k;
  78.     int A[n+5],opr[n+5],B[n+5];
  79.     ms(opr,0);
  80.     ff(i,1,n)
  81.     {
  82.     	cin>>A[i];
  83.     }
  84.     ff(i,1,n)
  85.     {
  86.     	cin>>B[i];
  87.     }
  88.     cin>>m;
  89.     while(m--)
  90.     {
  91.     	int l,r;
  92.     	cin>>l>>r;
  93.     	opr[l]+=1;
  94.     	opr[r+1]-=1;
  95.     }
  96.     ff(i,1,n)
  97.     {
  98.     	opr[i]+=opr[i-1];
  99.     }
  100.     ff(i,1,n)
  101.     {
  102.     	B[i]=B[i]+(opr[i]*(P[A[i]]<=k?1:0));
  103.     }
  104.     cin>>q;
  105.     while(q--)
  106.     {
  107.     	int x;
  108.     	cin>>x;
  109.     	cout<<B[x]<<endl;
  110.     }
  111.  
  112.     return 0;
  113. }
  114.  
Runtime error #stdin #stdout 0s 3952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xWFLhv
language:
C++ (gcc 8.3)
created:
7 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!