Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <hash_map>
- #include <algorithm>
- #include <utility>
- #include <functional>
- using namespace std;
- template <typename type> class LIS{
- private:
- std::vector<type> vector;
- int DP[50001];
- public:
- void insert(type value)
- {
- if (this->vector.empty() || this->vector.back() < value)
- {
- if (!this->vector.empty())
- this->DP[value] = this->vector.back();
- this->vector.push_back(value);
- }
- else
- {
- auto arg = std::lower_bound(this->vector.begin(), this->vector.end(), value);
- *arg = value;
- if (arg != this->vector.begin())
- this->DP[value] = *(--arg);
- }
- }
- std::vector<type> result()
- {
- int res = this->vector.back();
- this->vector.clear();
- while (res != 0){
- vector.push_back(res);
- res = DP[res];
- }
- std::sort(vector.begin(), vector.end());
- return vector;
- }
- unsigned long size()
- {
- return this->vector.size();
- }
- };
- int main()
- {
- long size;
- std::cin >> size;
- std::vector<std::pair<long, long> > vec;
- for (long i = 0; i < size; i++)
- {
- int p, q;
- std::cin >> p >> q;
- vec.push_back({ p, q });
- }
- sort(vec.begin(), vec.end());
- LIS<long> a;
- std::for_each(vec.begin(), vec.end(), [&a](std::pair<long, long> arg){a.insert(arg.second); });
- std::cout << vec.size() - a.size() << std::endl;
- std::vector<long > result = a.result();
- std::for_each(result.begin(), result.end(), [&vec](long args){
- for (std::pair<long, long> & arg : vec)
- if (arg.second == args)
- arg.first = 0;
- });
- std::for_each(vec.begin(), vec.end(), [](std::pair<long, long> arg){ if (arg.first) std::cout << arg.first << std::endl; });
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement