collecting_numbers_2216.cpp (816B)
1 #include <iostream> 2 #include <vector> 3 4 int main() { 5 size_t n, x, s{1}, l{0}; 6 std::cin >> n; 7 std::vector<size_t> b(n); 8 for (size_t i = 0; i < n; i++) { 9 std::cin >> x; 10 b[x-1] = i; 11 } 12 for (size_t i = 0; i < n; i++) { 13 s += b[i] < l; 14 l = b[i]; 15 } 16 std::cout << s << "\n"; 17 } 18 19 20 // The code below solves a different problem: it finds the minimum number 21 // of ascending chains needed to partition the given list of numbers. 22 23 #if 0 24 25 #include <algorithm> 26 #include <iostream> 27 #include <vector> 28 29 int main() { 30 size_t n; 31 std::vector<size_t> s; 32 std::cin >> n; 33 for (size_t i = 0; i < n; i++) { 34 size_t x; 35 std::cin >> x; 36 auto it = std::lower_bound( 37 s.begin(), s.end(), x, std::greater<size_t>()); 38 if (it != s.end()) 39 *it = x; 40 else 41 s.push_back(x); 42 } 43 std::cout << s.size() << std::endl; 44 } 45 46 #endif