#include <iostream> #include <algorithm> #include <math.h> using namespace std; typedef long long ll; const int rozmiar = 1e6 + 6; int pozycja[rozmiar]; int ciag[rozmiar]; int uzyte_min[rozmiar]; int uzyte_max[rozmiar]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; int akt_min; int akt_max; cin >> n; for (int i = 1; i <= n; i++) { cin >> ciag[i]; pozycja[ciag[i]] = i; } uzyte_min[1] = pozycja[n]; uzyte_max[1] = pozycja[n]; for (int i = 2; i <= n; i++) // i = rozmiar tablicy { uzyte_max[i] = max(uzyte_max[i - 1], pozycja[n - i/2]); uzyte_min[i] = min(uzyte_min[i - 1], pozycja[n - i/2]); } // rozwiazanie int wolne_pola; int w_prawo; int w_lewo; ll w_wynik = 0; for (int i = 1; i <= n; i++) { wolne_pola = i - (uzyte_max[i] - uzyte_min[i] + 1); if (wolne_pola < 0) { //cout << "WOLNE_POLA DLA: " << i << " LICZBA: " << wolne_pola << "\n"; continue; } w_prawo = n - uzyte_max[i]; w_lewo = uzyte_min[i] - 1; if (wolne_pola == w_prawo + w_lewo) ++w_wynik; else w_wynik += min(min(w_prawo, w_lewo), wolne_pola) + 1; //cout << "i:PRAWO:LEWO:WOLNEPOLA:wynik\n"; //cout << i << ":" << w_prawo << ":" << w_lewo << ":" << wolne_pola << ":" << w_wynik <<"\n"; //cout << "i:" << i << " " << w_wynik << "\n"; } cout << 2*n+1 << " " << w_wynik << "\n"; 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 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 64 65 66 67 68 69 70 71 72 | #include <iostream> #include <algorithm> #include <math.h> using namespace std; typedef long long ll; const int rozmiar = 1e6 + 6; int pozycja[rozmiar]; int ciag[rozmiar]; int uzyte_min[rozmiar]; int uzyte_max[rozmiar]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; int akt_min; int akt_max; cin >> n; for (int i = 1; i <= n; i++) { cin >> ciag[i]; pozycja[ciag[i]] = i; } uzyte_min[1] = pozycja[n]; uzyte_max[1] = pozycja[n]; for (int i = 2; i <= n; i++) // i = rozmiar tablicy { uzyte_max[i] = max(uzyte_max[i - 1], pozycja[n - i/2]); uzyte_min[i] = min(uzyte_min[i - 1], pozycja[n - i/2]); } // rozwiazanie int wolne_pola; int w_prawo; int w_lewo; ll w_wynik = 0; for (int i = 1; i <= n; i++) { wolne_pola = i - (uzyte_max[i] - uzyte_min[i] + 1); if (wolne_pola < 0) { //cout << "WOLNE_POLA DLA: " << i << " LICZBA: " << wolne_pola << "\n"; continue; } w_prawo = n - uzyte_max[i]; w_lewo = uzyte_min[i] - 1; if (wolne_pola == w_prawo + w_lewo) ++w_wynik; else w_wynik += min(min(w_prawo, w_lewo), wolne_pola) + 1; //cout << "i:PRAWO:LEWO:WOLNEPOLA:wynik\n"; //cout << i << ":" << w_prawo << ":" << w_lewo << ":" << wolne_pola << ":" << w_wynik <<"\n"; //cout << "i:" << i << " " << w_wynik << "\n"; } cout << 2*n+1 << " " << w_wynik << "\n"; return 0; } |