Saksham_Sahgal

Untitled

Mar 25th, 2022
1,057
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstring>
  3. #include<vector>
  4. #include<set>
  5. #include<map>
  6. #include<algorithm>
  7. #include<cmath>
  8. #include<climits>
  9. #define lli long long int
  10. #define GO_FAST ios_base::sync_with_stdio(0);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  11. // basic debugging macros
  12. lli __i__,__j__;
  13. lli inf = 9e18;
  14. #define line_printer(l) cout<<"\n"; for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl;
  15. #define array_printer(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<"\n";
  16. #define array_2d_printer(a,r,c) cout<<"\n"<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<"\n";}
  17. using namespace std;
  18.  
  19.  
  20.  
  21. int main()
  22. {
  23.     GO_FAST
  24.     int t;
  25.     cin>>t;
  26.     while(t)
  27.     {
  28.         lli n;
  29.         cin>>n;
  30.         lli a[n];
  31.         set<pair<lli,lli>> y;
  32.         for(int i=0;i<n;i++)
  33.             cin>>a[i];
  34.         map<lli,lli> ft;
  35.         y.insert({a[n-1],n-1});
  36.         for(int i=n-2;i>=0;i--)
  37.         {
  38.             y.insert({a[i],i});
  39.             //cout<<"at i = "<<i<<"\n";
  40.             auto ptr = (y.begin());
  41.             while( (ptr->first) != a[i])
  42.             {
  43.                 //cout<<"erasing"<<ptr->first<<"\n";
  44.  
  45.                 ft[ptr->second] = i;
  46.                // cout<<"from "<<i<<" to "<<ptr->second<<"\n";
  47.                 y.erase(y.begin());
  48.                 ptr = y.begin();
  49.             }
  50.         }
  51.  
  52.         lli dp[n] = {0};
  53.  
  54.         for(auto i:ft)
  55.         {
  56.             //cout<<i.first<<" "<<i.second<<"\n";
  57.             dp[i.first] = i.second;
  58.         }
  59.  
  60.         //array_printer(dp,n);
  61.         lli ans[n];
  62.         ans[0] = 0;
  63.         for(int i=1;i<n;i++)
  64.             ans[i] = ans[dp[i]] + 1;
  65.  
  66.         for(int i=0;i<n;i++)
  67.             cout<<ans[i]<<" ";
  68.  
  69.         cout<<"\n";
  70.         t--;
  71.     }
  72.     return 0;
  73. }
  74.  
  75.  
Advertisement
Add Comment
Please, Sign In to add comment