#include <cstdio> #include <vector> using namespace std; typedef long long LL; int main() { int n; scanf("%d", &n); vector<int> a(n); for (int i=0; i<n; ++i) scanf("%d", &a[i]); LL res = 0; int x = 0, y = n-1; for (int i=0; i<n; ++i) { int med = (n+1+i)/2; while (a[x] < med) ++x; while (a[y] < med) --y; // fprintf(stderr, "At %d - med %d\n", i, med); // fprintf(stderr, "(%d - %d)\n", x, y); int add = min(i, x) - max(y - n + i + 1, 0) + 1; // fprintf(stderr, "Add %d\n", add); if (add > 0) { res += add; } } printf("%d %lld\n", n*2 + 1, res); 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 | #include <cstdio> #include <vector> using namespace std; typedef long long LL; int main() { int n; scanf("%d", &n); vector<int> a(n); for (int i=0; i<n; ++i) scanf("%d", &a[i]); LL res = 0; int x = 0, y = n-1; for (int i=0; i<n; ++i) { int med = (n+1+i)/2; while (a[x] < med) ++x; while (a[y] < med) --y; // fprintf(stderr, "At %d - med %d\n", i, med); // fprintf(stderr, "(%d - %d)\n", x, y); int add = min(i, x) - max(y - n + i + 1, 0) + 1; // fprintf(stderr, "Add %d\n", add); if (add > 0) { res += add; } } printf("%d %lld\n", n*2 + 1, res); return 0; } |