1개의 댓글이 있습니다.

• 
  astein

  D번 stl::algorithm 에 있는 함수들을 이용해서 짠 n lg n LIS 코드입니다.
  ~~~ cpp

  #include
  #include
  #include
  using namespace std;
  int main()
  {
  int n, w, h;
  scanf("%d %d %d", &n, &w, &h);
  vector > > a;
  for (int i = 0; i < n; ++i)
  {
  int x, y;
  scanf("%d %d", &x, &y);
  if (x > w && y > h)
  {
  a.push_back( make_pair( x, make_pair( -y, i + 1 )));
  }
  }
  sort(a.begin(), a.end());
  for (int i = 0; i < a.size(); ++i)
  a[i].second.first *= -1;
  vector seq, ps;
  for (int i = 0; i < a.size(); ++i)
  {
  int pos = lower_bound( seq.begin(), seq.end(), a[i].second.first ) - seq.begin();
  if (pos == seq.size()) seq.push_back( -1 );
  seq[pos] = a[i].second.first;
  ps.push_back( pos );
  }
  printf("%d\n", seq.size());
  if (seq.size() == 0) return 0;
  vector res(seq.size());
  int gg = seq.size() - 1;
  for (int i = a.size() - 1; i >= 0; --i)
  {
  if (gg == ps[i])
  {
  res[gg] = a[i].second.second;
  gg--;
  }
  }
  for (int i = 0 ; i < seq.size(); ++i)
  {
  if (i != 0) printf(" ");
  printf("%d", res[i]);
  }
  printf("\n");
  }

  
  16년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.