#include <cstdio> #include <vector> #include <string> #include <algorithm> using namespace std; int cnt(int d, int l, int r, int n) { if (d > n) return 0; // printf("%d (%d %d) :: \n", d, l, r); if (r < d-1) r = d-1; if (l+d > n) l = n-d; if (r-l+1 > d) return 0; //r-d+1 .. l // printf("%d\n", l - (r-d+1) + 1); return l - (r-d+1) + 1; } int main() { int n; scanf("%d", &n); vector<int> p(n+1); for (int i = 0; i < n; i++) { int x; scanf("%d", &x); p[x] = i; } long long ret = 1; int l = p[n], r = p[n]; for (int i = n-1; i >= 1; i--) { l = std::min(l, p[i]); r = std::max(r, p[i]); int d = n-i; ret += cnt(d+d, l, r, n); ret += cnt(d+d+1, l, r, n); } printf("%d %lld\n",n+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 | #include <cstdio> #include <vector> #include <string> #include <algorithm> using namespace std; int cnt(int d, int l, int r, int n) { if (d > n) return 0; // printf("%d (%d %d) :: \n", d, l, r); if (r < d-1) r = d-1; if (l+d > n) l = n-d; if (r-l+1 > d) return 0; //r-d+1 .. l // printf("%d\n", l - (r-d+1) + 1); return l - (r-d+1) + 1; } int main() { int n; scanf("%d", &n); vector<int> p(n+1); for (int i = 0; i < n; i++) { int x; scanf("%d", &x); p[x] = i; } long long ret = 1; int l = p[n], r = p[n]; for (int i = n-1; i >= 1; i--) { l = std::min(l, p[i]); r = std::max(r, p[i]); int d = n-i; ret += cnt(d+d, l, r, n); ret += cnt(d+d+1, l, r, n); } printf("%d %lld\n",n+n+1, ret); return 0; } |