1개의 댓글이 있습니다.

• 
  astein

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

  #include <cstdio>
  #include <vector>
  #include <algorithm>
  using namespace std;
  int main()
  {
   int n, w, h;
   scanf("%d %d %d", &n, &w, &h);
   vector<pair<int, pair<int, int> > > 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<int> 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<int> 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");
  }
  

  
  14년 전 link

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