#include <bits/stdc++.h> using namespace std; using LL = long long; const int MAXN = 1000006; int n; int t[MAXN]; int poz[MAXN]; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &t[i]); poz[t[i]] = i; } LL res = 1; int l = poz[n]; int p = poz[n]; for (int i = n * 2 - 1; i >= n + 1; --i) { int actLen = 2 * n + 1 - i; if (i % 2 == 1) { // cout << "DODAJE " << i / 2 << " " << poz[i / 2] << endl; l = min(poz[i / 2], l); p = max(poz[i / 2], p); } if (p - l + 1 > actLen) { // cout << "skip dla " << i << endl; continue; } int rangeLen = p - l + 1; int seg = actLen - rangeLen; if (seg == 0) { ++res; // cout << "SEG 0 " << i << endl; continue; } int x = min(l - 1, seg); int y = min(n - p, seg); if (x < y) { swap(x, y); } int a = l - x; int minA = a + actLen - 1; int maksA = l + actLen - 1; int pom = maksA - minA + 1; int b = p + y - 1; if (b < maksA) { pom -= (maksA - b); } // cout << "Act rzeczy :: " << i << " " << actLen << " " << rangeLen << " " << l << " " << p << endl; // cout << i << " " << x << " " << y << " " << a << " " << b << " " << minA << " " << maksA << " " << pom << endl; res += max(0, pom + 1); // cout << i << " " << actLen << " " << l << " " << p << " " << rangeLen << " " << seg << endl; // cout << onLeft << " " << onRight << endl; // res += min(onRight, onLeft); } cout << 2 * n + 1 << " " << res << endl; }
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 60 61 62 63 | #include <bits/stdc++.h> using namespace std; using LL = long long; const int MAXN = 1000006; int n; int t[MAXN]; int poz[MAXN]; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &t[i]); poz[t[i]] = i; } LL res = 1; int l = poz[n]; int p = poz[n]; for (int i = n * 2 - 1; i >= n + 1; --i) { int actLen = 2 * n + 1 - i; if (i % 2 == 1) { // cout << "DODAJE " << i / 2 << " " << poz[i / 2] << endl; l = min(poz[i / 2], l); p = max(poz[i / 2], p); } if (p - l + 1 > actLen) { // cout << "skip dla " << i << endl; continue; } int rangeLen = p - l + 1; int seg = actLen - rangeLen; if (seg == 0) { ++res; // cout << "SEG 0 " << i << endl; continue; } int x = min(l - 1, seg); int y = min(n - p, seg); if (x < y) { swap(x, y); } int a = l - x; int minA = a + actLen - 1; int maksA = l + actLen - 1; int pom = maksA - minA + 1; int b = p + y - 1; if (b < maksA) { pom -= (maksA - b); } // cout << "Act rzeczy :: " << i << " " << actLen << " " << rangeLen << " " << l << " " << p << endl; // cout << i << " " << x << " " << y << " " << a << " " << b << " " << minA << " " << maksA << " " << pom << endl; res += max(0, pom + 1); // cout << i << " " << actLen << " " << l << " " << p << " " << rangeLen << " " << seg << endl; // cout << onLeft << " " << onRight << endl; // res += min(onRight, onLeft); } cout << 2 * n + 1 << " " << res << endl; } |