#include <iostream> #define ll long long int using namespace std; ll n; ll a; ll poz[1000001]; ll r; ll s, e; ll mins, maxs; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 1; i <= n; ++i) { cin >> a; poz[a] = i; } s = poz[n]; e = poz[n]; for (int i = 1; i <= n; ++i) { //cout << "[" << s << ", " << e << "] "; if (i % 2 == 0) { s = min(s, poz[n - (i / 2)]); e = max(e, poz[n - (i / 2)]); } mins = max((ll)1, 1 + e - i); maxs = min(1 + n - i, s); //cout << i << ": " << 1 + maxs - mins << " (" << mins << " - " << maxs << ")\n"; r += max(1 + maxs - mins, (ll)0); } cout << 2 * n + 1 << " " << r; }
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 <iostream> #define ll long long int using namespace std; ll n; ll a; ll poz[1000001]; ll r; ll s, e; ll mins, maxs; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 1; i <= n; ++i) { cin >> a; poz[a] = i; } s = poz[n]; e = poz[n]; for (int i = 1; i <= n; ++i) { //cout << "[" << s << ", " << e << "] "; if (i % 2 == 0) { s = min(s, poz[n - (i / 2)]); e = max(e, poz[n - (i / 2)]); } mins = max((ll)1, 1 + e - i); maxs = min(1 + n - i, s); //cout << i << ": " << 1 + maxs - mins << " (" << mins << " - " << maxs << ")\n"; r += max(1 + maxs - mins, (ll)0); } cout << 2 * n + 1 << " " << r; } |