http://www.spoj.pl/problems/LIS2/ i used nlogn code for this problem i gets wrong answer. here is my code. pls tell me where i went wrong pls. pls correct my code. Thanks in advance. int main() { int n; scanf("%d",&n); vector< pair<long int,long int> > v( n ); FOR(i,0,n) { int x,y; scanf("%d %d",&x,&y); v[i] = MP(x,y); } vector< pair<long int,long int> > lis; lis.PB(v[0]); FOR(i,1,v.SZ) { if ( v[i].FF > lis.back().FF && v[i].SS > lis.back().SS ) { lis.PB(v[i]); } else { long long int low = 0 ; long long int high = i-1; while ( low+1 < high ) { int mid = (low+high)/2; if ( lis[mid].FF < v[i].FF && lis[mid].SS < v[i].SS ) low = mid; else high = mid; } if ( high < lis.size() && v[i].FF < lis[high].FF && v[i].SS < lis[high].SS ) lis[ high ] = v[ i ]; } } printf("%d\n",lis.size()); }
-- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.