Link to this code:
https://cses.fi/paste/d860a70f95f193de60f051/#include<bits/stdc++.h> using namespace std; typedef long long int ll; #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>order_set; typedef pair<int, int>pr; #define all(i) i.begin() , i.end() #define ft first #define sn second #define pb push_back #define totalone(mask) __builtin_popcount(mask) #define chkbit(mask,bit) (mask&(1LL << bit)) #define setbit(mask,bit) (mask|(1LL << bit)) #define cngbit(mask,bit) (mask^(1LL << bit)) #define en "\n" #define dbg(x) cerr<<#x<<" is : "<<x<<en; #define yes cout<<"YES\n" #define no cout<<"NO\n" #define report cout<<-1<<en #define sum(n) ((1LL*(n)*(n+1))/ 2LL) #define sqr(n) (1LL*(n)*(n)) #define vag(a,b) ((a + b - 1)/b) #define coutv(v) for(auto i: v) cout<<i<<" ";cout<<en; #define cinv(v) for(auto &i: v) cin >> i; const int MAXN = 200005; #define inf 1e6+5 const int mod = 1e9 + 7; int n; int a[MAXN]; struct segment_tree { struct node { int suru , ses, cnt; void init(int l, int r) { suru = l, ses = r; if (l == r) cnt = 1; } } g[4 * MAXN]; void fill_cn(node &cn, node &ln, node &rn) // fill_current_node { cn.cnt = ln.cnt + rn.cnt; } void build(int cn, int l, int r) { g[cn].init(l, r); if (l == r ) return; int md = l + (r - l) / 2; build(cn * 2, l, md); build(cn * 2 + 1, md + 1, r); fill_cn (g[cn], g[cn * 2] , g[cn * 2 + 1]); } void update(int cn, int pos, int val) { int x = g[cn].suru; int y = g[cn].ses; if (y < pos || x > pos) return ; if (pos <= x && pos >= y ) { g[cn].cnt = 0; return; } update(cn * 2, pos, val); update(cn * 2 + 1, pos, val); fill_cn(g[cn], g[cn * 2], g[cn * 2 + 1]); } int query(int cn, int l, int r) { int x = g[cn].suru; int y = g[cn].ses; if (y < l || x > r) return 0; if (l <= x && r >= y ) return g[cn].cnt; int ans = query(cn * 2, l, r); ans += query(cn * 2 + 1, l, r); return ans; } } stre; void solve() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; stre.build(1, 1, n); for (int i = 1; i <= n; i++) { int x; cin >> x; int l = 1, r = n; int an; while (l <= r) { int md = l + (r - l) / 2; int cn = stre.query(1, 1, md); if (cn >= x) { an = md; r = md - 1; } else l = md + 1; } cout << a[an] << " "; stre.update(1, an, 0); } cout << en; } int main() { IOS; ll t; t = 1; // cin >> t; int c = 0; while ( t-- ) { // cout<<"Case "<<++c<<": "; solve(); } return 0; } 