fork download
copy 
  1. // Cách 1
  2. // Pass 2/11 Time Limit Exceed
  3. // ý tưởng bằng cách duyệt i [1, n-3] và j [2, n-2] tìm max planet trong đoạn [i, j] và lưu vào coupleMaxMP
  4. // sau đó lại duyệt từ i [0, n-2] và j [1, n-1]
  5. // và so sánh giá trị lớn nhất trong đoạn [i+1, j-1] ( tức coupleMaxMP[i+1, j-1])
  6. // với min planet [i] và [j]
  7. // nếu các planet bên trong đoạn [i, j] < giá trị của planet tại i, j thì tăng count lên
  8.  
  9. // #include <bits/stdc++.h>
  10. // #include <iostream>
  11. // using namespace std;
  12.  
  13. // int N; // 행성의 수 Number of planets
  14. // int W[100000 + 10]; // 행성 질량 Mass of planets
  15. // map<pair<int, int>, int> coupleMaxMP;
  16. // // int _count = 0;
  17.  
  18. // void InputData(void) {
  19. // 	cin >> N;
  20. // 	// cout<<"N = " << N << endl;
  21. // 	for (int i = 0; i < N; i++) {
  22. // 		cin >> W[i];
  23. // 	}
  24. // }
  25.  
  26. // int main(void) {
  27. // 	int ans = 0;
  28.  
  29. // 	InputData(); // 입력 Input
  30.  
  31. // 	// 코드를 작성하세요 Write from here
  32.  
  33. // 	// for (int i = 0; i <= N-2; i++) {
  34. // 	// 	coupleMaxMP[{i,i+1}] = max (W[i], W[i+1]);
  35. // 	// }
  36.  
  37. // 	for (int i = 1; i <= N-3; i++) {
  38. // 		for (int j = i+1; j <= N-2; j++) {
  39. // 			if (j == i+1) {
  40. // 				coupleMaxMP[{i, j}] = max (W[i], W[j]);
  41. // 			}
  42. // 			coupleMaxMP[{i, j}] = max (coupleMaxMP[{i, j-1}], W[j]);
  43. // 		}
  44. // 	}
  45.  
  46. // 	// cout<<"print coupleMaxMP" <<" begin" << endl;
  47. // 	// for (auto& xx: coupleMaxMP) {
  48. // 	// 	cout<<"[" << xx.first.first <<" " << xx.first.second <<"]: " << xx.second << endl;
  49. // 	// }
  50. // 	// cout<<"print coupleMaxMP" <<" end" << endl;
  51.  
  52. // 	ans = 0;
  53. // 	for (int i = 0; i <= N-2; i++) {
  54. // 		for (int j = i+1; j <= N-1; j++) {
  55. // 			if (j == i+1) {
  56. // 				ans++;
  57. // 			} else {
  58. // 				if (j == i+2) {
  59. // 					if (W[i+1] < W[i] && W[i+1] < W[j]) {
  60. // 						//found a config
  61. // 						ans++;
  62. // 					} else {
  63. // 						//nothing
  64. // 					}
  65. // 				} else { //j >= i+3
  66. // 					if (coupleMaxMP[{i+1, j-1}] < W[i] && coupleMaxMP[{i+1, j-1}] < W[j]) {
  67. // 						ans++;
  68. // 					} else {
  69. // 						//nothing
  70. // 					}
  71. // 				}
  72. // 			}
  73. // 		}
  74. // 	}
  75.  
  76. // 	cout << ans << endl; // 출력 Output
  77.  
  78. // 	return 0;
  79. // }
  80.  
  81. // =========================================================================
  82.  
  83. // // cách 2, tham khảo
  84. // // Pass 3/11 test case, TLE
  85. // // cách làm, cho đoạn i, j, tìm kiểm tra xem [i+1, j-1] có thỏa mãn max value([i+1, j-1]) < min (value(i, j))
  86. // #include <bits/stdc++.h>
  87. // #include <iostream>
  88. // using namespace std;
  89.  
  90. // int N; // Number of planets
  91. // int W[100000 + 10]; // Mass of planets
  92. // int ans = 0;
  93.  
  94. // void InputData(void) {
  95. // 	cin >> N;
  96. // 	for (int i = 0; i < N; i++) {
  97. // 		cin >> W[i];
  98. // 	}
  99. // }
  100.  
  101. // bool canTravel(int i, int j) {
  102. // 	if (j == i+1) {
  103. // 		return true;
  104. // 	} else {
  105. // 		int tmpMax = 0;
  106. // 		for (int k = i+1; k <= j-1; k++) {
  107. // 			tmpMax = max ( tmpMax, W[k]);
  108. // 		}
  109. // 		if (tmpMax < min(W[i], W[j])) return true;
  110. // 		else return false;
  111. // 	}
  112. // }
  113.  
  114. // int main(void) {
  115. // 	// int ans = -1;
  116.  
  117. // 	InputData(); // Input
  118.  
  119. // 	// Write code from here
  120.  
  121. // 	for (int i = 0; i <= N-2; i++) {
  122. // 		for (int j = i+1; j <= N-1; j++) {
  123. // 			if (canTravel(i, j) == true) ans++;
  124. // 		}
  125. // 	}
  126.  
  127. // 	cout << ans << endl; // Output
  128.  
  129. // 	return 0;
  130. // }
  131.  
  132. // =========================================================================
  133. // cách 3
  134. // Pass 5/11 Time Limit Exceed
  135. // cách làm, su dung two pointers, i chay tu 0 den N-2, j chay tu i+1 den N-1
  136. // tai moi diem j dang xet, tìm max của đoạn [i+1, j-1] ,
  137. // nếu như nhỏ hơn min đoạn (i, j) thì tăng biến đếm lên, và tiếp tục
  138. // nếu ko thỏa mãn, không tăng biến đếm, thì vẫn tăng j lên để tìm đoạn phù hợp
  139.  
  140. #include <bits/stdc++.h>
  141. using namespace std;
  142.  
  143. int N; // Number of planets
  144. int W[100000 + 10]; // Mass of planets
  145. int ans = 0;
  146.  
  147. void InputData(void) {
  148.     cin >> N;
  149.     for (int i = 0; i < N; i++) {
  150.         cin >> W[i];
  151.     }
  152. }
  153.  
  154. int main(void) {
  155.     InputData(); // Input
  156.  
  157.     for (int i = 0; i <= N - 2; i++) {
  158.         int tmpMax = W[i + 1]; // Bắt đầu từ phần tử liền kề
  159.         for (int j = i + 1; j <= N - 1; j++) {
  160.             if (j == i + 1) { 
  161.                 // Cặp lân cận luôn hợp lệ
  162.                 ans++;
  163.             } else {
  164.                 // Cập nhật giá trị lớn nhất của đoạn [i+1, j-1]
  165.                 tmpMax = max(tmpMax, W[j - 1]);
  166.                 // Kiểm tra điều kiện giữa hai hành tinh
  167.                 if (tmpMax < min(W[i], W[j])) {
  168.                     ans++;
  169.                 } else {
  170.                     // Nếu không hợp lệ, vẫn tiếp tục kiểm tra, không break,
  171. 										// bởi vì vẫn có thể tìm thấy k thuộc [i, j] thỏa mãn
  172.                 }
  173.             }
  174.         }
  175.     }
  176.  
  177.     cout << ans << endl; // Output
  178.     return 0;
  179. }
  180.  
  181.  
  182. // =========================================================================
  183. // cach 4 AI
  184. // dung two pointers, Pass 5/11, Time limit
  185. // #include <iostream>
  186. // #include <vector>
  187. // #include <algorithm>
  188.  
  189. // using namespace std;
  190.  
  191. // int main() {
  192. //     int n;
  193. //     cin >> n;
  194.  
  195. //     vector<int> w(n);
  196. //     for (int i = 0; i < n; ++i) {
  197. //         cin >> w[i];
  198. //     }
  199.  
  200. //     int count = 0;
  201. //     for (int i = 0; i < n; ++i) {
  202. //         for (int j = i + 1; j < n; ++j) {
  203. //             bool possible = true;
  204. //             int left = i + 1;
  205. //             int right = j - 1;
  206.  
  207. //             if (left <= right) {
  208. //                 for (int k = left; k <= right; ++k) {
  209. //                     if (w[k] >= w[i] || w[k] >= w[j]) {
  210. //                         possible = false;
  211. //                         break;
  212. //                     }
  213. //                 }
  214. //             }
  215. //             if (possible) {
  216. //                 count++;
  217. //             }
  218. //         }
  219. //     }
  220.  
  221. //     cout << count << endl;
  222.  
  223. //     return 0;
  224. // }
  225.  
  226. // =========================================================================
  227. // cach 5 AI brute force
  228. // Pass 5/11, Time Limit
  229. // #include <iostream>
  230. // #include <vector>
  231. // using namespace std;
  232.  
  233. // int countTravelablePairs(const vector<int>& masses) {
  234. //     int n = masses.size();
  235. //     int count = 0;
  236.  
  237. //     for (int i = 0; i < n; ++i) {
  238. //         for (int j = i + 1; j < n; ++j) {
  239. //             bool canTravel = true;
  240. //             for (int k = i + 1; k < j; ++k) {
  241. //                 if (masses[k] >= masses[i] || masses[k] >= masses[j]) {
  242. //                     canTravel = false;
  243. //                     break;
  244. //                 }
  245. //             }
  246. //             if (canTravel) {
  247. //                 count++;
  248. //             }
  249. //         }
  250. //     }
  251.  
  252. //     return count;
  253. // }
  254.  
  255. // int main() {
  256. //     int n;
  257. //     cin >> n;
  258. //     vector<int> masses(n);
  259. //     for (int i = 0; i < n; ++i) {
  260. //         cin >> masses[i];
  261. //     }
  262.  
  263. //     int result = countTravelablePairs(masses);
  264. //     cout << result << endl;
  265.  
  266. //     return 0;
  267. // }
  268.  
  269.  
  270. // =========================================================================
  271.  
  272. // cách 6 theo khảo ý anh Mạnh
  273. // tại mỗi planet k,
  274. // tìm planet i ở phía trên phải mà có giá trị max
  275. // tìm planet j ở phía trên phải mà có giá trị max
  276. // chưa triển khai được
  277.  
  278.  
  279. // =========================================================================
  280. // =========================================================================
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Be1Q3E
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!