#include <iostream> #include <algorithm> using namespace std; int n, lewy, prawy; long long wynik; pair<int, int> p[1000001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> p[i].first; p[i].second = i; } sort(p+1, p+n+1); lewy = n; prawy = 1; for (int i = n; i > 0; i--) { lewy = min(lewy, p[i].second); prawy = max(prawy, p[i].second); if (i == n) wynik++; else { int dlugosc = prawy - lewy + 1; int oczekiwana_dlugosc = 2 * (n-i); if (oczekiwana_dlugosc > n) break; if (dlugosc <= oczekiwana_dlugosc) { int lewyk = max(1, prawy - oczekiwana_dlugosc + 1); int prawyk = min(n, lewy + oczekiwana_dlugosc - 1); prawyk -= oczekiwana_dlugosc - 1; wynik += prawyk - lewyk + 1; } oczekiwana_dlugosc++; if (oczekiwana_dlugosc > n) break; if (dlugosc <= oczekiwana_dlugosc) { int lewyk = max(1, prawy - oczekiwana_dlugosc + 1); int prawyk = min(n, lewy + oczekiwana_dlugosc - 1); prawyk -= oczekiwana_dlugosc - 1; wynik += prawyk - lewyk + 1; } } } cout << 2*n+1 << ' '<< wynik << 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 | #include <iostream> #include <algorithm> using namespace std; int n, lewy, prawy; long long wynik; pair<int, int> p[1000001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> p[i].first; p[i].second = i; } sort(p+1, p+n+1); lewy = n; prawy = 1; for (int i = n; i > 0; i--) { lewy = min(lewy, p[i].second); prawy = max(prawy, p[i].second); if (i == n) wynik++; else { int dlugosc = prawy - lewy + 1; int oczekiwana_dlugosc = 2 * (n-i); if (oczekiwana_dlugosc > n) break; if (dlugosc <= oczekiwana_dlugosc) { int lewyk = max(1, prawy - oczekiwana_dlugosc + 1); int prawyk = min(n, lewy + oczekiwana_dlugosc - 1); prawyk -= oczekiwana_dlugosc - 1; wynik += prawyk - lewyk + 1; } oczekiwana_dlugosc++; if (oczekiwana_dlugosc > n) break; if (dlugosc <= oczekiwana_dlugosc) { int lewyk = max(1, prawy - oczekiwana_dlugosc + 1); int prawyk = min(n, lewy + oczekiwana_dlugosc - 1); prawyk -= oczekiwana_dlugosc - 1; wynik += prawyk - lewyk + 1; } } } cout << 2*n+1 << ' '<< wynik << endl; } |