#include <iostream> #include <vector> void solution() { int n; std::cin >> n; std::vector<int> tab(n); std::vector<int> indices(n + 1); for (int i = 0; i < n; ++i) { std::cin >> tab[i]; indices[tab[i]] = i; } // dla przedzialu jednoelemntowego zawierającego n long long counter = 1; // przedział minimalny int left = indices[n]; int right = indices[n]; for (int length = 2; length <= n; ++length) { if (length % 2 == 0) { if (indices[n - length / 2] < left) { left = indices[n - length / 2]; } else if (indices[n - length / 2] > right) { right = indices[n - length / 2]; } } // sprawdzamy, czy przedział nam pasuje do długości // buffer = ile "miejsca" zostało nam do wykorzystania int buffer = length - (right - left + 1); if (buffer >= 0) { int LL = std::max(buffer - left, 0); int LR = buffer; int RL = 0; int RR = std::min(n - 1 - right, buffer); int L = std::max(LL, RL); int R = std::min(LR, RR); counter += R - L + 1; } } std::cout << 2 * n + 1 << " " << counter << "\n"; } int main() { solution(); 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 | #include <iostream> #include <vector> void solution() { int n; std::cin >> n; std::vector<int> tab(n); std::vector<int> indices(n + 1); for (int i = 0; i < n; ++i) { std::cin >> tab[i]; indices[tab[i]] = i; } // dla przedzialu jednoelemntowego zawierającego n long long counter = 1; // przedział minimalny int left = indices[n]; int right = indices[n]; for (int length = 2; length <= n; ++length) { if (length % 2 == 0) { if (indices[n - length / 2] < left) { left = indices[n - length / 2]; } else if (indices[n - length / 2] > right) { right = indices[n - length / 2]; } } // sprawdzamy, czy przedział nam pasuje do długości // buffer = ile "miejsca" zostało nam do wykorzystania int buffer = length - (right - left + 1); if (buffer >= 0) { int LL = std::max(buffer - left, 0); int LR = buffer; int RL = 0; int RR = std::min(n - 1 - right, buffer); int L = std::max(LL, RL); int R = std::min(LR, RR); counter += R - L + 1; } } std::cout << 2 * n + 1 << " " << counter << "\n"; } int main() { solution(); return 0; } |