Skip to content

Instantly share code, notes, and snippets.

@jiunbae
Created July 16, 2015 18:53
Show Gist options
  • Save jiunbae/d8648566b28b7c2fc004 to your computer and use it in GitHub Desktop.
Save jiunbae/d8648566b28b7c2fc004 to your computer and use it in GitHub Desktop.
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment