Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- int const N = 200010;
- ll fenwick[N];
- ll query(ll x){
- ll sum = 0;
- for(int i = x ; i >= 1 ; i -= (i&-i)){
- sum += fenwick[i];
- }
- return sum;
- }
- void update(ll x){
- for(int i = x ; i <= N ; i += (i&-i)){
- fenwick[i]++;
- }
- }
- int main()
- {
- //freopen("input.txt","r",stdin);
- int n;
- scanf("%d",&n);
- ll arr[n+1];
- bool check[n+1];
- for(int i = 1 ; i <= n ; i ++){
- scanf("%lld",&arr[i]);
- check[i] = false;
- }
- for(int t = 0 ; t < n ; t ++){
- ll x;
- scanf("%lld",&x);
- //// printf("Test : ");for(int i = 1 ; i <= n ; i ++)printf("%d ",i);printf("\n");
- // printf("Index : ");
- ll l = 1 , r = n;
- while(l<=r){
- ll m = (l+r)/2;
- ll xi = m - query(m);
- if(xi == x){
- if(check[m]){
- r = m - 1;
- }
- else{
- printf("%lld\n",arr[m]);
- update(m);
- check[m] = true;
- break;
- }
- }
- else if(xi > x){
- r = m - 1;
- }
- else{
- l = m + 1;
- }
- }
- /* for(int i = 1 ; i <= n ; i ++){
- ll xi = i - query(i);
- // printf("%lld ",xi);
- if(xi == x){
- // printf("Test found");
- printf("%lld\n",arr[i]);
- update(i);
- break;
- }
- }
- // printf("\n");*/
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement