#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { cin.tie(0); ios_base::sync_with_stdio(0); long long n; cin >> n; long long ans=1; if (n > 1) ans++; vector <long long> v(n), vpos(n); for (long long i = 0; i < n; i++) { cin >> v[i]; vpos[v[i] - 1] = i; } long long minp = min(vpos.back(), vpos[n-2]), maxp = max(vpos.back(), vpos[n - 2]); long long front = minp, back = n-1 - maxp; for (long long i = 2, j = 2; i < n; i++) { if (maxp - minp + 1 <= i) ans += 1 + min(front, i - (maxp - minp + 1)) + min(back, i - (maxp - minp + 1)) -(i- (maxp - minp + 1)); if (i % 2 == 1) { j++; minp = min(minp, vpos[n - j]); maxp = max(maxp, vpos[n - j]); front = minp; back = n - 1 - maxp; } } cout << 2 * n + 1 << " " << ans << "\n"; }
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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { cin.tie(0); ios_base::sync_with_stdio(0); long long n; cin >> n; long long ans=1; if (n > 1) ans++; vector <long long> v(n), vpos(n); for (long long i = 0; i < n; i++) { cin >> v[i]; vpos[v[i] - 1] = i; } long long minp = min(vpos.back(), vpos[n-2]), maxp = max(vpos.back(), vpos[n - 2]); long long front = minp, back = n-1 - maxp; for (long long i = 2, j = 2; i < n; i++) { if (maxp - minp + 1 <= i) ans += 1 + min(front, i - (maxp - minp + 1)) + min(back, i - (maxp - minp + 1)) -(i- (maxp - minp + 1)); if (i % 2 == 1) { j++; minp = min(minp, vpos[n - j]); maxp = max(maxp, vpos[n - j]); front = minp; back = n - 1 - maxp; } } cout << 2 * n + 1 << " " << ans << "\n"; } |