#include <cstdio> #include <algorithm> using namespace std; int t[1000001]; int p[1000001]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", t + i); p[t[i]] = i; } long long ret = 1; int l = p[n]; int r = p[n]; int c = 1; for (int i = n - 1; i >= (n + 1) / 2; i--) { int a = p[i]; if (a < l) { l = a; } else if (a > r) { r = a; } int k = r - l + 1; c++; if (k == c) { ret++; } if (k < c) { int r1 = min(c - k, l - 1); int r2 = min(c - k, n - r); int a1 = c - k - r1; int a2 = c - k; int b1 = 0; int b2 = r2; if (a1 <= b2) { ret += b2 - a1 + 1; } } if (n % 2 == 0 && i == n / 2) { break; } c++; if (k == c) { ret++; } if (k < c) { int r1 = min(c - k, l - 1); int r2 = min(c - k, n - r); int a1 = c - k - r1; int a2 = c - k; int b1 = 0; int b2 = r2; if (a1 <= b2) { ret += b2 - a1 + 1; } } } printf("%d %lld\n", 2 * n + 1, ret); 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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | #include <cstdio> #include <algorithm> using namespace std; int t[1000001]; int p[1000001]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", t + i); p[t[i]] = i; } long long ret = 1; int l = p[n]; int r = p[n]; int c = 1; for (int i = n - 1; i >= (n + 1) / 2; i--) { int a = p[i]; if (a < l) { l = a; } else if (a > r) { r = a; } int k = r - l + 1; c++; if (k == c) { ret++; } if (k < c) { int r1 = min(c - k, l - 1); int r2 = min(c - k, n - r); int a1 = c - k - r1; int a2 = c - k; int b1 = 0; int b2 = r2; if (a1 <= b2) { ret += b2 - a1 + 1; } } if (n % 2 == 0 && i == n / 2) { break; } c++; if (k == c) { ret++; } if (k < c) { int r1 = min(c - k, l - 1); int r2 = min(c - k, n - r); int a1 = c - k - r1; int a2 = c - k; int b1 = 0; int b2 = r2; if (a1 <= b2) { ret += b2 - a1 + 1; } } } printf("%d %lld\n", 2 * n + 1, ret); return 0; } |