#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
int main() {
int n;
std::cin >> n;
std::vector<int> pearls(n);
for (int i = 0; i < n; i++) {
std::cin >> pearls[i];
}
auto it = std::max_element(pearls.begin(), pearls.end());
int idx = it - pearls.begin();
std::rotate(pearls.begin(), pearls.begin() + idx, pearls.end());
std::set<std::pair<int,int>> active;
active.insert({pearls[0], 1});
int result = 1;
for (int i = n - 1; i > 0; i--) {
auto it = active.upper_bound({pearls[i], 0});
if (it->first == pearls[i]) {
active.erase(it);
it = active.upper_bound({pearls[i], 0});
}
if (it == active.end()) {
active.insert({pearls[i], 1});
} else {
result = std::max(result, (*it).second + 1);
active.insert({pearls[i], (*it).second + 1});
}
while (!active.empty()) {
auto it = active.begin();
if ((*it).first < pearls[i]) {
active.erase(active.begin());
} else {
break;
}
}
}
std::cout << result << std::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 45 | #include <set> #include <vector> #include <iostream> #include <algorithm> #include <iterator> int main() { int n; std::cin >> n; std::vector<int> pearls(n); for (int i = 0; i < n; i++) { std::cin >> pearls[i]; } auto it = std::max_element(pearls.begin(), pearls.end()); int idx = it - pearls.begin(); std::rotate(pearls.begin(), pearls.begin() + idx, pearls.end()); std::set<std::pair<int,int>> active; active.insert({pearls[0], 1}); int result = 1; for (int i = n - 1; i > 0; i--) { auto it = active.upper_bound({pearls[i], 0}); if (it->first == pearls[i]) { active.erase(it); it = active.upper_bound({pearls[i], 0}); } if (it == active.end()) { active.insert({pearls[i], 1}); } else { result = std::max(result, (*it).second + 1); active.insert({pearls[i], (*it).second + 1}); } while (!active.empty()) { auto it = active.begin(); if ((*it).first < pearls[i]) { active.erase(active.begin()); } else { break; } } } std::cout << result << std::endl; return 0; } |
English