fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool comp(pair<int,pair<int,int> > a,pair<int,pair<int,int> > b){
  5.     if(a.second.first<b.second.first) return true;
  6.     else if(a.second.first==b.second.first){
  7.         if(a.second.second<=b.second.second) return true;
  8.         else return false;
  9.     }
  10.     return false;
  11. }
  12. /*
  13. vector<pair<int,pair<int,int> > > LIS(vector<pair<int,pair<int,int> > > envp){
  14.    vector< vector<pair<int,pair<int,int> > > > L(envp.size());
  15.     L[0].push_back(envp[0]); 
  16.   
  17.     for (int i = 1; i < envp.size(); i++) 
  18.     { 
  19.         for (int j = 0; j < i; j++) 
  20.         { 
  21.             if ((envp[i].second.first > envp[j].second.first && envp[i].second.second > envp[j].second.second) && 
  22.                     (L[i].size() < L[j].size() + 1)) 
  23.                 L[i] = L[j]; 
  24.         } 
  25.         L[i].push_back(envp[i]); 
  26.     } 
  27.  
  28.     vector<pair<int,pair<int,int> > > ma = L[0]; 
  29.   
  30.     // LIS will be max of all increasing sub- 
  31.     // sequences of arr 
  32.     for (vector<pair<int,pair<int,int> > > x : L) 
  33.         if (x.size() > ma.size()) 
  34.             ma = x; 
  35.   
  36.     return ma;
  37. }
  38. */
  39. // Binary search 
  40. int GetCeilIndex(vector<pair<int,pair<int,int> > > envp, vector<int>& T, int l, int r, 
  41.                  pair<int,pair<int,int> > key) 
  42. { 
  43.     while (r - l > 1) { 
  44.         int m = l + (r - l) / 2; 
  45.         if ((envp[T[m]].second.first > key.second.first && envp[T[m]].second.second > key.second.second)) 
  46.             r = m; 
  47.         else
  48.             l = m; 
  49.     } 
  50.  
  51.     return r; 
  52. } 
  53.  
  54. vector<pair<int,pair<int,int> > > LIS(vector<pair<int,pair<int,int> > > envp) 
  55. { 
  56.     // Add boundary case, when array n is zero 
  57.     // Depend on smart pointers 
  58.  
  59.     vector<int> tailIndices(envp.size(), 0); // Initialized with 0 
  60.     vector<int> prevIndices(envp.size(), -1); // initialized with -1 
  61.  
  62.     int len = 1; // it will always point to empty location 
  63.     for (int i = 1; i < envp.size(); i++) { 
  64.         if (envp[i].second.first < envp[tailIndices[0]].second.first && envp[i].second.second < envp[tailIndices[0]].second.second) { 
  65.             // new largest value 
  66.             tailIndices[0] = i; 
  67.         } 
  68.         else if (envp[i].second.first > envp[tailIndices[len-1]].second.first && envp[i].second.second > envp[tailIndices[len-1]].second.second) { 
  69.             // arr[i] wants to extend largest subsequence 
  70.             prevIndices[i] = tailIndices[len - 1]; 
  71.             tailIndices[len++] = i; 
  72.         } 
  73.         else { 
  74.             // arr[i] wants to be a potential condidate of 
  75.             // future subsequence 
  76.             // It will replace ceil value in tailIndices 
  77.             int pos = GetCeilIndex(envp, tailIndices, -1, 
  78.                                    len - 1, envp[i]); 
  79.  
  80.             prevIndices[i] = tailIndices[pos - 1]; 
  81.             tailIndices[pos] = i; 
  82.         } 
  83.     } 
  84.  
  85.     //cout << "LIS of given input" << endl;
  86.     vector<pair<int,pair<int,int> > > out;
  87.  
  88.     for (int i = tailIndices[len - 1]; i >= 0; i = prevIndices[i]) 
  89.         out.push_back(envp[i]);
  90.     //cout << endl; 
  91.  
  92.     return out; 
  93. }
  94.  
  95. int main(){
  96.     int n,wl,hl;
  97.     cin>>n>>wl>>hl;
  98.  
  99.     vector<pair<int,pair<int,int> > > envp;
  100.     int wi,hi;
  101.     for(int i=0;i<n;i++){
  102.         cin>>wi>>hi;
  103.         if(wi>wl && hi>hl) envp.push_back(make_pair(i+1,make_pair(wi,hi)));
  104.     }
  105.     if(envp.size()<1) {
  106.     	cout<<"0"<<endl;
  107.     	return 0;
  108.     }
  109.     sort(envp.begin(),envp.end(),comp);
  110.  
  111. 	/*for (pair<int,pair<int,int> > x : envp) 
  112.         printf("(%d(%d,%d))\n",x.first,x.second.first,x.second.second);
  113.     */
  114.     vector<pair<int,pair<int,int> > > ma;
  115.  
  116.     ma=LIS(envp);
  117. 	cout<<ma.size()<<endl;
  118.     for (int i=ma.size()-1;i>=0;i--) 
  119.         cout<<ma[i].first<<" ";
  120.     //cout<<endl;
  121.  
  122.     return 0;
  123. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3 3 3
5 4
12 11
9 8
stdout
copy 
3
1 3 2
https://ideone.com/yQMrJ5
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!