fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Numeric Constants
  5. #define N 1000000007
  6. #define maxs 200005
  7. #define mins 1005
  8. #define eps 1e-14
  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 vals[maxs],val2[maxs],col[maxs];
  34. vector<int>v;
  35. int tree[maxs],colors[maxs];
  36.  
  37. void update(int ind,int val){
  38. 	while(ind<=2000){
  39. 		tree[ind]=max(tree[ind],val);
  40. 		ind+=(ind & -ind);
  41. 	}
  42. }
  43.  
  44. int query(int ind){
  45. 	int ret=0;
  46. 	while(ind>0){
  47. 		ret=max(ret,tree[ind]);
  48. 		ind-=(ind & -ind);
  49. 	}
  50. 	return ret;
  51. }
  52.  
  53. int main()
  54. {
  55. 	int n,i,j,k,q,len;
  56. 	sc("%d",&n);
  57. 	for(i=0;i<n;i++){
  58. 		sc("%d",&vals[i]);
  59. 		val2[i]=vals[i];
  60. 	}	
  61. 	sort(val2,val2+n);
  62. 	for(i=0;i<n;i++){
  63. 		vals[i]=lower_bound(val2,val2+n,vals[i])-val2+1;
  64. 	}
  65. 	for(i=0;i<n;i++){
  66. 		sc("%d",&col[i]);
  67. 		col[i]--;
  68. 	}
  69. 	for(i=0;i<=n;i++){
  70. 		colors[i]=imax;
  71. 	}
  72. 	for(i=0;i<(1<<10);i++){
  73. 		v.clear();
  74. 		for(j=0;j<n;j++){
  75. 			if((1<<col[j])&i){
  76. 				v.pb(vals[j]);
  77. 			}
  78. 		}
  79. 		for(j=0;j<=2000;j++){
  80. 			tree[j]=0;
  81. 		}
  82. 		int ans=0;
  83. 		for(k=0;k<v.size();k++){
  84. 			int q=query(v[k]);
  85. 			ans=max(ans,q+1);
  86. 			update(v[k],q+1);
  87. 		}
  88. 		int tt=__builtin_popcount(i);
  89. 		for(j=ans;j>=0;j--){
  90. 			colors[j]=min(colors[j],tt);
  91. 		}
  92. 	}
  93. 	sc("%d",&q);
  94. 	for(i=0;i<q;i++){
  95. 		sc("%d",&len);
  96. 		if(len>n){
  97. 			pr("-1\n");
  98. 			continue;
  99. 		}
  100. 		if(colors[len]>=imax){
  101. 			pr("-1\n");
  102. 		}
  103. 		else{
  104. 			pr("%d\n",colors[len]);
  105. 		}
  106. 	}
  107. 	return 0;
  108. }
Runtime error #stdin #stdout 0.06s 7376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/l7XZu0
language:
C++14 (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!