#include <iostream> #include <vector> using namespace std; typedef long long int lint; int ile_przedzialow(int n, int k, int min_index, int max_index) { if (max_index - min_index >= k) { return 0; } int min_ust = max(0, max_index - k + 1); int max_ust = min(n - k, min_index); if (max_ust < min_ust) { return 0; } else { return max_ust - min_ust + 1; } } int main() { ios_base::sync_with_stdio(0); int n; cin >> n; vector<int> pozycja(n + 1, -1); for (int i = 0; i < n; ++i) { int a; cin >> a; pozycja[a] = i; } lint suma = 1; // zaczynamy od wpisania do sumy jednoelementowego przedzialu int min_index = pozycja[n]; int max_index = pozycja[n]; for (int k = 2; k <= n; ++k) { if (k % 2 == 0) { int wymagany_element = n - k/2; int index = pozycja[wymagany_element]; min_index = min(min_index, index); max_index = max(max_index, index); } suma += ile_przedzialow(n, k, min_index, max_index); } cout << 2*n + 1 << ' ' << suma << endl; 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 | #include <iostream> #include <vector> using namespace std; typedef long long int lint; int ile_przedzialow(int n, int k, int min_index, int max_index) { if (max_index - min_index >= k) { return 0; } int min_ust = max(0, max_index - k + 1); int max_ust = min(n - k, min_index); if (max_ust < min_ust) { return 0; } else { return max_ust - min_ust + 1; } } int main() { ios_base::sync_with_stdio(0); int n; cin >> n; vector<int> pozycja(n + 1, -1); for (int i = 0; i < n; ++i) { int a; cin >> a; pozycja[a] = i; } lint suma = 1; // zaczynamy od wpisania do sumy jednoelementowego przedzialu int min_index = pozycja[n]; int max_index = pozycja[n]; for (int k = 2; k <= n; ++k) { if (k % 2 == 0) { int wymagany_element = n - k/2; int index = pozycja[wymagany_element]; min_index = min(min_index, index); max_index = max(max_index, index); } suma += ile_przedzialow(n, k, min_index, max_index); } cout << 2*n + 1 << ' ' << suma << endl; return 0; } |