#include <bits/stdc++.h> using namespace std; using LL = long long; #define FOR(i, l, r) for(int i = (l); i <= (r); ++i) #define REP(i, n) FOR(i, 0, (n) - 1) #define ssize(x) int(x.size()) template<class A, class B> auto& operator<<(ostream &o, pair<A, B> p) { return o << '(' << p.first << ", " << p.second << ')'; } template<class T> auto operator<<(ostream &o, T x) -> decltype(x.end(), o) { o << '{'; int i = 0; for(auto e : x) o << (", ")+2*!i++ << e; return o << '}'; } ostream& operator<<(ostream &o, string &s) { return o << s.data(); } #ifdef DEBUG #define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n' #else #define debug(...) {} #endif int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<int> a(n), pos(n); REP(i, n) { cin >> a[i]; a[i]--; pos[a[i]] = i; } auto fnd_ans = [&](int l, int r, int val) { int side = val - (r - l + 1); if (side < 0) return 0LL; if (r + 1 >= val) return (LL) min({side + 1, l + 1, n - r}); int out = val - (r + 1); return (LL) min({side + 1, l + 1, n - r - out}); }; int l = pos[n - 1]; int r = l, x; LL ans = 1; for (int i = 2; i <= (n + 2) / 2; i++) { l = min(l, pos[n - i]); r = max(r, pos[n - i]); x = i * 2 - 2; ans += fnd_ans(l, r, x); x++; if (x <= n) ans += fnd_ans(l, r, x); } cout << 2 * n + 1 << ' ' << ans << '\n'; 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 | #include <bits/stdc++.h> using namespace std; using LL = long long; #define FOR(i, l, r) for(int i = (l); i <= (r); ++i) #define REP(i, n) FOR(i, 0, (n) - 1) #define ssize(x) int(x.size()) template<class A, class B> auto& operator<<(ostream &o, pair<A, B> p) { return o << '(' << p.first << ", " << p.second << ')'; } template<class T> auto operator<<(ostream &o, T x) -> decltype(x.end(), o) { o << '{'; int i = 0; for(auto e : x) o << (", ")+2*!i++ << e; return o << '}'; } ostream& operator<<(ostream &o, string &s) { return o << s.data(); } #ifdef DEBUG #define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n' #else #define debug(...) {} #endif int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<int> a(n), pos(n); REP(i, n) { cin >> a[i]; a[i]--; pos[a[i]] = i; } auto fnd_ans = [&](int l, int r, int val) { int side = val - (r - l + 1); if (side < 0) return 0LL; if (r + 1 >= val) return (LL) min({side + 1, l + 1, n - r}); int out = val - (r + 1); return (LL) min({side + 1, l + 1, n - r - out}); }; int l = pos[n - 1]; int r = l, x; LL ans = 1; for (int i = 2; i <= (n + 2) / 2; i++) { l = min(l, pos[n - i]); r = max(r, pos[n - i]); x = i * 2 - 2; ans += fnd_ans(l, r, x); x++; if (x <= n) ans += fnd_ans(l, r, x); } cout << 2 * n + 1 << ' ' << ans << '\n'; return 0; } |