Skip to content

Instantly share code, notes, and snippets.

@jiunbae
Created September 26, 2015 11:23
Show Gist options
  • Save jiunbae/3c7e52cec1d2edf1c06b to your computer and use it in GitHub Desktop.
Save jiunbae/3c7e52cec1d2edf1c06b to your computer and use it in GitHub Desktop.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template <typename type>
struct Comp {
Comp(type val) : _val(val) {}
bool operator() (const pair<type, vector<type>> & vec) const
{
for (type v : vec.second)
if (v == this->_val)
return true;
return false;
}
private:
type _val;
};
int main()
{
long long int n, k;
for (;;)
{
cin >> n >> k;
if (!n && !k)
break;
vector<pair<long long int, vector<long long int>>> tree;
vector<long long int> v;
tree.push_back({ 0, v });
long long int ttemp = 0, pp = 0, p = 0, p_counter = 0;
for (int i = 0; i < n; i++)
{
long long int temp;
cin >> temp;
if (tree.size() == 1)
ttemp = temp;
if (ttemp + 1 < temp)
{
p_counter++;
if (p_counter >= tree.at(pp).second.size())
{
p_counter = 0;
pp = p;
p = tree.size() - tree.at(p).second.size();
}
}
if (temp == k)
k = tree.size();
tree.at(p + p_counter).second.push_back(tree.size());
tree.push_back({ temp,v });
ttemp = temp;
}
vector<pair<long long int, vector<long long int>>>::iterator it = find_if(tree.begin(), tree.end(), Comp<long long int>(k));
if (it == tree.end())
{
cout << "0" << endl;
continue;
}
vector<pair<long long int, vector<long long int>>>::iterator iit = find_if(tree.begin(), tree.end(), Comp<long long int>(it - tree.begin()));
if (iit == tree.end())
cout << "0" << endl;
else
{
int size = 0;
for (int p : iit->second)
if (tree.at(p).first != it->first)
size += tree.at(p).second.size();
cout << size << endl;
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment