My-Implementations/SegmentTree.cpp at master · cenation092/My-Implementations · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// Question Link: https://www.interviewbit.com/problems/order-of-people-heights/

#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<array>
#include<cstdio>
#include<bitset>
#include<vector>
#include<utility>
#include<sstream>
#include<cstring>
#include <climits>
#include <fstream>
#include<iostream>
#include<algorithm>
#include <functional>
#define mp make_pair
using namespace std;

struct one_node{
    int sum;
    int idx;
    void leaf(int sum, int idx){
        this->sum = sum;
        this->idx = idx;
    }
    void merge( one_node &n1, one_node &n2 ){
        sum = n1.sum + n2.sum;
        idx = max( n1.idx, n2.idx);
    }
};

one_node tree[1000000];

void build( int node, int l, int r ){
    // leaf
    if( l == r ){
        tree[node].leaf(1, l);
        return;
    }
    int mid = (l+r)/2;
    int left_node = node*2;
    int right_node = node*2+1;
    build(left_node, l, mid);
    build(right_node, mid+1, r);
    tree[node].merge(tree[left_node], tree[right_node]);
}

void update( int node, int l, int r, int idx ){
    //position used
    if( l == r ){
        tree[node].leaf(0, -1);
        return;
    }
    int mid = (l+r)/2;
    int left_node = node*2;
    int right_node = node*2+1;
    if( idx <= mid )update(left_node, l, mid, idx);
    else update(right_node, mid+1, r, idx);
    tree[node].merge(tree[left_node], tree[right_node]);
}

int query( int node, int l, int r, int sum ){
    // required position
    if( tree[node].sum == sum ){
        return tree[node].idx;
    }
    int mid = (l+r)/2;
    int left_node = node*2;
    int right_node = node*2+1;
    if( tree[left_node].sum >= sum ){ // exist in left
        int sum_left = sum;
        return query(left_node, l, mid, sum_left);
    }
    else{ // exist in right
        int sum_left = sum - tree[left_node].sum;
        return query(right_node, mid+1, r, sum_left);
    }
}

int main(){
    int n;
    cin >> n;
    int h[n], b[n];
    build(1, 0, n-1);
    vector<pair<int,int> > Ar;
    for( int i = 0; i < n; i++ ){
        cin >> h[i];
    }
    for( int i = 0; i < n; i++ ){
        cin >> b[i];
        Ar.push_back(make_pair(h[i], b[i]));
    }
    sort( Ar.begin(), Ar.end());
    int ans[n];
    for( int i = 0; i < n; i++ ){
        int sum = Ar[i].second + 1;
        int idx = query(1, 0, n-1, sum);
        update(1, 0, n-1, idx);
        ans[idx] = Ar[i].first;
    }
    for( int i = 0; i < n; i++ ){
        cout << ans[i] << " ";
    }
}