#include <bits/stdc++.h> using namespace std; #ifdef D #define DEBUG(x) \ do { \ x \ cout.flush(); \ } while (0) #else #define DEBUG(x) #endif const int NMAX = 1e6 + 7; int n, m, l, r; int t[NMAX], pos[NMAX]; long long c; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 0; i < n; ++i) { cin >> t[i]; pos[t[i]] = i; } m = 2 * n + 1; l = r = pos[n]; for (int i = 1; i <= n; ++i) { if (i % 2 == 0) { if (pos[n - i / 2] < l) { l = pos[n - i / 2]; } else if (pos[n - i / 2] > r) { r = pos[n - i / 2]; } } c += max(0, min(l + i - 1, n - 1) - max(0, r - i + 1) - i + 2); // DEBUG(cout << i << ": " << c << " " << l << " " << r << "\n";); } cout << m << " " << c; 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 | #include <bits/stdc++.h> using namespace std; #ifdef D #define DEBUG(x) \ do { \ x \ cout.flush(); \ } while (0) #else #define DEBUG(x) #endif const int NMAX = 1e6 + 7; int n, m, l, r; int t[NMAX], pos[NMAX]; long long c; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 0; i < n; ++i) { cin >> t[i]; pos[t[i]] = i; } m = 2 * n + 1; l = r = pos[n]; for (int i = 1; i <= n; ++i) { if (i % 2 == 0) { if (pos[n - i / 2] < l) { l = pos[n - i / 2]; } else if (pos[n - i / 2] > r) { r = pos[n - i / 2]; } } c += max(0, min(l + i - 1, n - 1) - max(0, r - i + 1) - i + 2); // DEBUG(cout << i << ": " << c << " " << l << " " << r << "\n";); } cout << m << " " << c; return 0; } |