Gild Puzzle 320: Gymnast Tower

g320.cc

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

struct comp {
  bool operator() (const pair <int, int> i, const pair <int, int> j) const
  { return (i.first<j.first); }
} compobj;

struct comp2 {
  bool operator() (const pair <int, int> i, const pair <int, int> j) const
  { return (i.second<j.second); }
} comp2obj;

set < pair<int, int> , comp > gymnast;
set < pair<int, int> > checks;

int main(int argc, char** argv) {
  FILE * pFile = fopen (argv[1], "r");

  int a, b;
  while (fscanf(pFile, "(%d, %d) ", &a, &b) == 2) {
    gymnast.insert(make_pair(a, b));
  }

  set< pair<int, int> >::iterator it = gymnast.begin();
  checks.insert(make_pair(it->second, 0));
  it++;
  // For each one in the topological order
  for (; it != gymnast.end(); it++) {
    // Look back in the edge list
    set <pair<int, int> >::iterator upperbound = checks.upper_bound(make_pair(it->second, 0));
    checks.insert(make_pair(it->second, upperbound != checks.begin() ?
          (max_element(checks.begin(), upperbound, comp2obj)->second + 1) : 0
          ));
  }

  printf("%d\n", max_element(checks.begin(), checks.end(), comp2obj)->second + 1);
    return 0;
}