fork(1) download 
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct node{
  8.     string s;
  9.     int val;
  10. };
  11.  
  12. struct node2{
  13.     node x;
  14.     node2 *left, *right;
  15.  
  16.     node2(node &t) : x(t), left(NULL), right(NULL){}
  17. };
  18.  
  19. struct seg_tree{
  20.     pair<int, int> seg[200001];
  21.  
  22.     void build(int l, int r, int i);
  23.     int query(int l, int r, int i, int x, int y);
  24. };
  25.  
  26. node arr[50001];
  27.  
  28. void seg_tree :: build(int l, int r, int i){
  29.     if(l == r){
  30.         seg[i].first = arr[l].val;
  31.         seg[i].second = l;
  32.         return;
  33.     }
  34.     int mid = (l+r)/2;
  35.     build(l, mid, i*2+1);
  36.     build(mid+1, r, i*2+2);
  37.  
  38.     if(seg[i*2+1].first > seg[i*2+2].first) seg[i] = seg[i*2+1];
  39.     else seg[i] = seg[i*2+2];
  40. }
  41.  
  42. int seg_tree :: query(int l, int r, int i, int x, int y){
  43.     if(r < x || l > y) return -1;
  44.     if(l >= x && r <= y) return seg[i].second;
  45.     int mid = (l+r)/2;
  46.     int left = query(l, mid, i*2+1, x, y);
  47.     int right = query(mid+1, r, i*2+2, x, y);
  48.  
  49.     if(left == right) return left;
  50.     else if(left == -1) return right;
  51.     else if(right == -1) return left;
  52.  
  53.     if(arr[left].val > arr[right].val) return left;
  54.     else return right;
  55. }
  56.  
  57. int n;
  58.  
  59. seg_tree *s;
  60.  
  61. bool cmp1(node& a, node& b){
  62.     return a.s < b.s;
  63. }
  64.  
  65. bool cmp2(int& a, int& b){
  66.     return a > b;
  67. }
  68.  
  69. node2* build(int l, int r){
  70.     if(l > r) return NULL;
  71.     if(l == r){
  72.         node2* temp = new node2(arr[l]);
  73.         return temp;
  74.     }
  75.     int pos = s -> query(0, n-1, 0, l, r);
  76.     node2* curr = new node2(arr[pos]);
  77.     curr->left = build(l, pos-1);
  78.     curr->right = build(pos+1, r);
  79.     return curr;
  80. }
  81.  
  82. void inorder(node2* root){
  83.     if(!root) return;
  84.     cout << "(";
  85.     inorder(root->left);
  86.     cout << root->x.s << "/" << root->x.val;
  87.     inorder(root->right);
  88.     cout << ")";
  89. }
  90.  
  91. int main(){
  92.     cin >> n;
  93.     while(n != 0){
  94.         s = new seg_tree;
  95.  
  96.         for(int k = 0; k < n; k++){
  97.             string s, curr = "";
  98.             cin >> s;
  99.             int t = s.length(), j = 0, data = 0;
  100.  
  101.             while(s[j] != '/')
  102.                 curr += s[j++];
  103.             j++;
  104.             while(j < t){
  105.                 data = data*10 + s[j] - '0';
  106.                 j++;
  107.             }
  108.             arr[k].s = curr;
  109.             arr[k].val = data;
  110.         }
  111.  
  112.         sort(arr, arr+n, cmp1);
  113.  
  114.         s->build(0, n-1, 0);
  115.         node2* ans = build(0, n-1);
  116.         inorder(ans);
  117.         cout << endl;
  118.  
  119.         cin >> n;
  120.     }
  121.     return 0;
  122. }
  123.  
Success #stdin #stdout 0s 21896KB
comments (?)
stdin 
7 a/7 b/6 c/5 d/4 e/3 f/2 g/1
7 a/1 b/2 c/3 d/4 e/5 f/6 g/7
7 a/3 b/6 c/4 d/7 e/2 f/5 g/1
0
stdout 
(a/7(b/6(c/5(d/4(e/3(f/2(g/1)))))))
(((((((a/1)b/2)c/3)d/4)e/5)f/6)g/7)
(((a/3)b/6(c/4))d/7((e/2)f/5(g/1)))
https://ideone.com/wSaUA7
language:
C++14 (gcc 8.3)
created:
7 years 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!