#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> a(n); vector<int> pos(n+1); for(int i = 0; i < n; i++){ cin>>a[i]; pos[a[i]] = i; } vector<bool> removable(n, false); long long ways = 1; for(int i = 1; i <= (n/2); i++){ removable[pos[i]] = true; } int l = -1; int r = n; for(int j = 1; j <= n-1; j++){ removable[pos[(n + j - 1)/2]] = true; while(removable[l+1])l++; while(removable[r-1])r--; int L = l+1; int R = n - r; ways += max(0, min(j, L) - max(j-R, 0) + 1); } cout<<(2*n+1)<<" "<<ways<<"\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 | #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> a(n); vector<int> pos(n+1); for(int i = 0; i < n; i++){ cin>>a[i]; pos[a[i]] = i; } vector<bool> removable(n, false); long long ways = 1; for(int i = 1; i <= (n/2); i++){ removable[pos[i]] = true; } int l = -1; int r = n; for(int j = 1; j <= n-1; j++){ removable[pos[(n + j - 1)/2]] = true; while(removable[l+1])l++; while(removable[r-1])r--; int L = l+1; int R = n - r; ways += max(0, min(j, L) - max(j-R, 0) + 1); } cout<<(2*n+1)<<" "<<ways<<"\n"; } |