#include <bits/stdc++.h> using namespace std; int fn(int a, int b, int k) { if (k < 0) return 0; a = min(a, k); b = min(b, k); return max(a + b - k + 1, 0); } int main() { int n; scanf("%d", &n); vector<int> v(n); vector<int> rv(n); vector<bool> rb(n, false); for (int i = 0; i < n; i++) { scanf("%d", &v[i]); rv[--v[i]] = i; } rb[n-1] = true; int ca = 1; long long wyn = 1; int p = rv[n-1]; int q = p; for (int i = n-2; i >= 0; i--) { while (p > rv[i]) { p--; rb[v[p]] = true; ca++; } while (q < rv[i]) { q++; rb[v[q]] = true; ca++; } int l = n-i; wyn += fn(p, n-q-1, 2*l-ca-1); wyn += fn(p, n-q-1, 2*l-ca-2); } printf("%d %lld", n*2+1, wyn); }
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 | #include <bits/stdc++.h> using namespace std; int fn(int a, int b, int k) { if (k < 0) return 0; a = min(a, k); b = min(b, k); return max(a + b - k + 1, 0); } int main() { int n; scanf("%d", &n); vector<int> v(n); vector<int> rv(n); vector<bool> rb(n, false); for (int i = 0; i < n; i++) { scanf("%d", &v[i]); rv[--v[i]] = i; } rb[n-1] = true; int ca = 1; long long wyn = 1; int p = rv[n-1]; int q = p; for (int i = n-2; i >= 0; i--) { while (p > rv[i]) { p--; rb[v[p]] = true; ca++; } while (q < rv[i]) { q++; rb[v[q]] = true; ca++; } int l = n-i; wyn += fn(p, n-q-1, 2*l-ca-1); wyn += fn(p, n-q-1, 2*l-ca-2); } printf("%d %lld", n*2+1, wyn); } |