#include <bits/stdc++.h> #define int long long using namespace std; signed main() { int n; cin >> n; unordered_map<int, int> m; int n_pos, biggest_pos, smallest_pos, res; res = 1; for (int i = 0; i < n; i++) { int x; cin >> x; if (x == n) { n_pos = biggest_pos = smallest_pos = i; } m[x] = i; } for (int i = n - 1; i >= (n + 1) / 2; i--) { int position = m[i]; int iter = n - i + 1; smallest_pos = min(smallest_pos, position); biggest_pos = max(biggest_pos, position); int segment_width = biggest_pos - smallest_pos + 1; for (int segment_checked : {iter * 2 - 2, iter * 2 - 1}) { int first_beg = max(0LL, biggest_pos - segment_checked + 1); int last_beg = min(smallest_pos, n - segment_checked); // cerr << segment_checked << " " << first_beg << " " << last_beg << endl; if (segment_width <= segment_checked) { res += last_beg - first_beg + 1; } } } cout << 2 * n + 1 << " " << res << endl; }
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 | #include <bits/stdc++.h> #define int long long using namespace std; signed main() { int n; cin >> n; unordered_map<int, int> m; int n_pos, biggest_pos, smallest_pos, res; res = 1; for (int i = 0; i < n; i++) { int x; cin >> x; if (x == n) { n_pos = biggest_pos = smallest_pos = i; } m[x] = i; } for (int i = n - 1; i >= (n + 1) / 2; i--) { int position = m[i]; int iter = n - i + 1; smallest_pos = min(smallest_pos, position); biggest_pos = max(biggest_pos, position); int segment_width = biggest_pos - smallest_pos + 1; for (int segment_checked : {iter * 2 - 2, iter * 2 - 1}) { int first_beg = max(0LL, biggest_pos - segment_checked + 1); int last_beg = min(smallest_pos, n - segment_checked); // cerr << segment_checked << " " << first_beg << " " << last_beg << endl; if (segment_width <= segment_checked) { res += last_beg - first_beg + 1; } } } cout << 2 * n + 1 << " " << res << endl; } |