fork(1) download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <queue>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. int red=0;
  8. int blue=1;
  9.  
  10. struct E{
  11. 	int color,r,height;
  12. };
  13. struct E2{
  14. 	int color;
  15. 	int commit;
  16. 	int len;
  17. 	int height;
  18. 	int no;
  19. 	int count;
  20. };
  21. struct E3{
  22. 	int right,commit;
  23. 	bool operator<(const E3& e3)const{
  24. 		if(right!=e3.right)return right<e3.right;
  25. 		return commit<e3.commit;
  26. 	}
  27. };
  28.  
  29. map<E3,long long int> perm;
  30. vector<E> vs;
  31. queue<E2> qs;
  32. int main() {
  33. 	int r1=1;
  34. 	int n,m;
  35. 	cin>>n>>m;
  36. 	for(int i=0;i<n;i++){
  37. 		E e1;
  38. 		cin>>e1.height;
  39. 		e1.color=red;
  40. 		e1.r=r1;
  41. 		vs.push_back(e1);
  42. 		r1*=2;
  43. 	}
  44. 	for(int i=0;i<m;i++){
  45. 		E e1;
  46. 		cin>>e1.height;
  47. 		e1.color=blue;
  48. 		e1.r=r1;
  49. 		vs.push_back(e1);
  50. 		r1*=2;
  51. 	}
  52. 	for(int i=0;i<vs.size();i++){
  53. 		E e1=vs[i];
  54. 		E2 e2;
  55. 		E3 e3;
  56. 		e3.right=i;
  57. 		e3.commit=e1.r;
  58. 		perm[e3]=1;
  59. 		e2.color=e1.color;
  60. 		e2.commit=e1.r;
  61. 		e2.len=1;
  62. 		e2.height=e1.height;
  63. 		e2.no=i;
  64. 		e2.count=1;
  65. 		qs.push(e2);
  66. 	}
  67. 	long long int ans=0;
  68. 	while(qs.size()>0){
  69. 		E2 e2=qs.front();
  70. 		qs.pop();
  71. 		if(e2.count==n+m){
  72. 			if(1<e2.len){
  73. 				E3 e3;
  74. 				e3.right=e2.no;
  75. 				e3.commit=e2.commit;
  76. 				ans+=perm[e3];
  77. 				cout<<e3.right<<" "<<e3.commit<<" "<<e2.len<<" "<<perm[e3]<<endl;
  78. 			}
  79. 			continue;
  80. 		}
  81.  
  82. 		for(int i=0;i<n+m;i++){
  83. 			E e1=vs[i];
  84. 			if((e2.commit & e1.r)>0)continue;
  85. 			E2 e2next;
  86. 			e2next.commit=e2.commit+e1.r;
  87. 			e2next.height=e1.height;
  88. 			e2next.color=e1.color;
  89. 			e2next.no=i;
  90. 			e2next.count=e2.count+1;
  91. 			E3 e3now,e3next;
  92. 			e3now.right=e2.no;
  93. 			e3now.commit=e2.commit;
  94. 			e3next.right=i;
  95. 			e3next.commit=e2next.commit;
  96.  
  97. 			if(e2.color==e1.color && e2.height<e1.height){
  98. 				e2next.len=e2.len+1;
  99. 				if(perm.find(e3next)==perm.end()){
  100. 					qs.push(e2next);
  101. 					perm[e3next]=0;
  102. 				}
  103. 				perm[e3next]+=perm[e3now];
  104. 			}else if(1<e2.len && e2.height>e1.height && e2.color!=e1.color){
  105. 				e2next.len=1;
  106. 				if(perm.find(e3next)==perm.end()){
  107. 					qs.push(e2next);
  108. 					perm[e3next]=0;
  109. 				}
  110. 				perm[e3next]+=perm[e3now];
  111. 			}
  112. 		}
  113. 	}
  114. 	cout<<ans<<endl;
  115. 	return 0;
  116. }
Success #stdin #stdout 0.85s 30076KB
comments (?)
stdin
copy 
8 8
12 2 11 13 9 8 15 10
6 1 16 7 14 3 4 5
stdout
copy 
15 65535 3 3307713
11 65535 4 4665278
7 65535 3 962276
12 65535 6 1118024
10 65535 4 1000016
8 65535 4 3759029
6 65535 4 1705878
3 65535 4 1700334
18218548
https://ideone.com/15KpfH
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

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!