fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. #include <cstring>
  6.  
  7. using namespace std;
  8.  
  9. const int maxN = 600000;
  10. vector<int> t[2 * maxN];
  11. int n, a[maxN], b[maxN];
  12. map<int, int> pos;
  13.  
  14. vector<int> d[maxN];
  15. int p[maxN];
  16.  
  17. void build(int i, int l, int r) {
  18. 	if (l == r) {
  19. 		t[i] = vector<int>(1, b[l]);
  20. 	} else {
  21. 		build(2 * i, l, (l + r) / 2);
  22. 		build(2 * i + 1, (l + r) / 2 + 1, r);
  23. 		t[i].resize(t[2 * i].size() + t[2 * i + 1].size());
  24. 		merge(t[2 * i].begin(), t[2 * i].end(), t[2 * i + 1].begin(), t[2 * i + 1].end(), t[i].begin());
  25. 	}
  26. }
  27.  
  28. int get(int i, int cl, int cr, int l, int r, int value) {
  29. 	if (l > r) {
  30. 		return n;
  31. 	}
  32. 	if (cl == l && r == cr) {
  33. 		int index = upper_bound(t[i].begin(), t[i].end(), value) - t[i].begin();
  34. 		if (index == t[i].size()) {
  35. 			return n;
  36. 		}
  37. 		return t[i][index];
  38. 	}
  39.  
  40. 	if (l > (cl + cr) / 2) {
  41. 		return get(2 * i + 1, (cl + cr) / 2 + 1, cr, l, r, value);
  42. 	}
  43. 	if (r <= (cl + cr) / 2) {
  44. 		return get(2 * i, cl, (cl + cr) / 2, l, r, value);
  45. 	}
  46.  
  47. 	int A = get(2 * i, cl, (cl + cr) / 2, l, (cl + cr) / 2, value);
  48. 	int B = get(2 * i + 1, (cl + cr) / 2 + 1, cr, (cl + cr) / 2 + 1, r, value);
  49. 	return min(A, B);
  50. }
  51.  
  52. int main() {
  53. 	memset(b, -1, sizeof(b));
  54. 	scanf("%d", &n);
  55. 	for (int i = 0; i < n; ++i) {
  56. 		scanf("%d", &a[i]);
  57. 	}
  58. 	for (int i = n - 1; i >= 0; --i) {
  59. 		if (pos.count(a[i])) {
  60. 			b[i] = pos[a[i]];
  61. 		}
  62. 		pos[a[i]] = i;
  63. 	}
  64. 	build(1, 0, n - 1);
  65. 	p[n] = n;
  66. 	d[n] = vector<int>(2, -1);
  67. 	for (int i = n - 1; i >= 0; --i) {
  68. 		int j = b[i];
  69. 		if (j == -1) {
  70. 			p[i] = p[i + 1];
  71. 			d[i] = d[i + 1];
  72. 			continue;
  73. 		}
  74.  
  75. 		int value = get(1, 0, n - 1, i + 1, j - 1, j);
  76. 		if (value == n) {
  77. 			p[i] = p[i + 1];
  78. 			d[i] = d[i + 1];
  79. 		} else {
  80. 			p[i] = value;
  81. 			d[i].push_back(a[i]);
  82. 			d[i].push_back(a[value]);
  83. 		}
  84.  
  85. 		if (p[i + 1] < p[i]) {
  86. 			p[i] = p[i + 1];
  87. 			d[i] = d[i + 1];
  88. 		}
  89.  
  90. 		int k = b[j];
  91. 		if (k != -1) {
  92. 			int l = b[k];
  93. 			if (l != -1 && l < p[i]) {
  94. 				p[i] = l;
  95. 				d[i] = vector<int>(2, a[i]);
  96. 			}
  97. 		}
  98. 	}
  99.  
  100. 	vector<int> res;
  101. 	int start = 0;
  102. 	while (start < n) {
  103. 		if (p[start] != n) {
  104. 			res.push_back(d[start][0]);
  105. 			res.push_back(d[start][1]);
  106. 			res.push_back(d[start][0]);
  107. 			res.push_back(d[start][1]);
  108. 			start = p[start] + 1;
  109. 		} else {
  110. 			break;
  111. 		}
  112. 	}
  113. 	printf("%d\n", res.size());
  114. 	for (int i = 0; i < res.size(); ++i) {
  115. 		printf("%d ", res[i]);
  116. 	}
  117. 	printf("\n");
  118. 	return 0;
  119. }
Success #stdin #stdout 0.02s 31568KB
comments (?)
stdin
copy 
10
35 1 2 1 2 35 100 200 100 200
stdout
copy 
8
1 2 1 2 100 200 100 200
https://ideone.com/BJwBGq
language:
C++14 (gcc 8.3)
created:
9 years 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!