[editorial] codeforces #4

1개의 댓글이 있습니다.
  • astein
    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");
    }
    

    8년 전 link
  • 댓글을 남기시려면 로그인하세요.