fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. using namespace std;
  4. int find(vector<int>v,int pos)
  5. {
  6.     if(upper_bound(v.begin(),v.end(),pos)!=v.end())
  7.     return 1;
  8.     return 0;
  9. }
  10. void solve()
  11. {
  12.   string s;
  13.   cin>>s;
  14.   unordered_map<char,vector<int>>mp;
  15.   for(int i=0;i<s.size();i++)
  16.   {
  17.       mp[s[i]].push_back(i);
  18.   }
  19.   set<char>st;
  20.   stack<char>stk;
  21.   stk.push(s[0]);
  22.   st.insert(s[0]);
  23.   for(int i=1;i<s.size();i++)
  24.   {
  25.       if(st.find(s[i])!=st.end())
  26.       continue;
  27.  
  28.       while((!stk.empty()) && (s[i]>stk.top()) && find(mp[stk.top()],i))
  29.       {
  30.           st.erase(stk.top());
  31.           stk.pop();
  32.       }
  33.       stk.push(s[i]);
  34.       st.insert(s[i]);
  35.   }
  36.  
  37.   string ans="";
  38.   while(!stk.empty()){
  39.       ans+=stk.top();
  40.       stk.pop();
  41.   }
  42.   reverse(ans.begin(),ans.end());
  43.   cout<<ans<<"\n";
  44. }
  45. int main()
  46. {
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(NULL);
  49.     cout.tie(NULL);
  50.     ll t;
  51.     cin>>t;
  52.     while(t--)
  53.     {
  54.         solve();
  55.     }
  56. }
Runtime error #stdin #stdout 0.01s 4920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy
https://ideone.com/XiOUta
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!