View difference between Paste ID: 6zaKbKRS and ytYDayy0

 /*
 Longest Non-Decreasing Subsequence
 Vremenska slozenost: O(N*logN)
 Memorija: O(N)
 */
 
 #include <bits/stdc++.h>
 using namespace std;
 
 const int N=1e5+10;
 
 struct Node
 {
     int parent;
     Node()
     {
         parent=-1;
     }
 } g[N]; //graf (stablo) koji sluzi za rekonstrukciju LISa
 
 int n, a[N], dp[N], lis; // dp[i] <==> idx najmanjeg broja kom je LIS duzine i
 vector<int> sol; //rekonstruisan LIS
 
 int bs (int x, int bound) //hocu broj X da stavim na postojeci LIS duzine RET
 {
-    int l=0, r=bound, mid, ret=0;
+    int l=1, r=bound, mid, ret=0;
     while (l<=r)
     {
         mid=l+(r-l)/2;
         if (dp[mid]==-1 || a[dp[mid]]>x) r=mid-1;
         else
         {
             ret=mid;
             l=mid+1;
         }
     }
     return ret+1; //novi LIS ce biti duzine RET+1
 }
 
 void dfs (int v)
 {
     sol.push_back(v);
     if (g[v].parent==-1) return;
     dfs (g[v].parent);
 }
 
 void reconstruct ()
 {
     dfs (dp[lis]);
     reverse (sol.begin(), sol.end()); //tehnicki suvisno
 }
 
 int main()
 {
     scanf ("%d", &n);
     memset (dp, -1, sizeof dp);
 
     for (int i=1;i<=n;i++)
     {
         scanf ("%d", &a[i]);
 
         int idx=bs(a[i], i-1);
         lis=max(lis, idx);
 
         if (dp[idx]==-1 || a[dp[idx]]>a[i])
         {
             dp[idx]=i;
             if (idx>1) g[i].parent=dp[idx-1]; //koja pozicija je u LISu pre i
         }
     }
 
     reconstruct();
 
     printf ("%d\n", lis);
     for (int i=0;i<lis;i++) printf ("%d ", a[sol[i]]);
 
     return 0;
 }