#include <iostream> int n; int t[1000005]; int r[1000005]; void input() { std::cin >> n; for (int i = 0; i < n; i++) { int k; std::cin >> k; t[i] = k; r[k] = i; } } int max(int a, int b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } void solve() { int start = r[n]; int end = r[n]; long long result = 0; for (int k = 1; k <= n; k++) { int next = n - k / 2; start = min(start, r[next]); end = max(end, r[next]); int len = end - start + 1; // std::cout << k << " " << next << " " << start << " " << end << " " << len << "\n"; if (len == k) { // std::cout << "result++ " << result << "\n"; result++; } else if (len < k) { int max_end = min(start + k - 1, n - 1); int min_start = max(end - k + 1, 0); result += (max_end - min_start) - k + 2; // std::cout << max_end << " " << min_start << " " << (max_end - min_start) - k + 2 << "\n"; } } std::cout << 2 * n + 1 << " " << result << "\n"; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); input(); solve(); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <iostream> int n; int t[1000005]; int r[1000005]; void input() { std::cin >> n; for (int i = 0; i < n; i++) { int k; std::cin >> k; t[i] = k; r[k] = i; } } int max(int a, int b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } void solve() { int start = r[n]; int end = r[n]; long long result = 0; for (int k = 1; k <= n; k++) { int next = n - k / 2; start = min(start, r[next]); end = max(end, r[next]); int len = end - start + 1; // std::cout << k << " " << next << " " << start << " " << end << " " << len << "\n"; if (len == k) { // std::cout << "result++ " << result << "\n"; result++; } else if (len < k) { int max_end = min(start + k - 1, n - 1); int min_start = max(end - k + 1, 0); result += (max_end - min_start) - k + 2; // std::cout << max_end << " " << min_start << " " << (max_end - min_start) - k + 2 << "\n"; } } std::cout << 2 * n + 1 << " " << result << "\n"; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); input(); solve(); return 0; } |