fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct SegTree {
  5.     int n;
  6.     vector<char> tree;
  7.  
  8.     SegTree(const string &s) {
  9.         int sz = s.size();
  10.         n = 1;
  11.         while (n < sz) n <<= 1;
  12.         tree.assign(2 * n, char(127));
  13.         for (int i = 0; i < sz; i++) {
  14.             tree[n + i] = s[i];
  15.         }
  16.         for (int i = n - 1; i > 0; i--) {
  17.             tree[i] = min(tree[2 * i], tree[2 * i + 1]);
  18.         }
  19.     }
  20.  
  21.     char range_min(int l, int r) {
  22.         char res = char(127);
  23.         l += n;
  24.         r += n;
  25.         while (l < r) {
  26.             if (l & 1) res = min(res, tree[l++]);
  27.             if (r & 1) res = min(res, tree[--r]);
  28.             l >>= 1;
  29.             r >>= 1;
  30.         }
  31.         return res;
  32.     }
  33. };
  34.  
  35. int main() {
  36.     string S;
  37.     cin >> S;
  38.     int N = S.size();
  39.  
  40.     SegTree seg(S);
  41.  
  42.     vector<char> st;
  43.     string ans;
  44.  
  45.     for (int i = 0; i < N; i++) {
  46.         st.push_back(S[i]);
  47.         char min_suffix = (i + 1 < N) ? seg.range_min(i + 1, N) : char(127);
  48.         while (!st.empty() && st.back() <= min_suffix) {
  49.             ans += st.back();
  50.             st.pop_back();
  51.         }
  52.     }
  53.  
  54.     cout << ans << "\n";
  55. }
  56.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/PqHJqe
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
7 hours 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!