Table Sum Problem Code: INOI1202 Solution

 #include <bits/stdc++.h>
using namespace std;
vector<int> a;
int n;
vector<int> arr,heap;
// i is heap index
// arr[i] should give index of current element in original input array
// i -> arr[i]
// heap[i] should give index of i-th original element in heap
// heap[original_idx] -> current idx in heap
void heapify_down(int i){
    int max_idx=-1,max_val=INT_MIN;
    if(2*i<=n&&a[2*i]>max_val)max_val=a[2*i],max_idx=2*i;
    if(2*i+1<=n&&a[2*i+1]>max_val)max_val=a[2*i+1],max_idx=2*i+1;
    if(max_idx!=-1&&max_val>a[i]){
        // cout<<"haha";
        int apar=arr[i],achil=arr[max_idx];
        heap[apar]=max_idx;
        heap[achil]=i;
        arr[i]^=arr[max_idx];
        arr[max_idx]^=arr[i];
        arr[i]^=arr[max_idx];
        a[i]^=a[max_idx];
        a[max_idx]^=a[i];
        a[i]^=a[max_idx];
        heapify_down(max_idx);
    }
}
void heapify_up(int i){
    if(i==1)return;
    if(i/2>0&&a[i]>a[i/2]){
        a[i/2]^=a[i];
        a[i]^=a[i/2];
        a[i/2]^=a[i];
        int apar=arr[i],achil=arr[i/2];
        heap[apar]=i/2;
        heap[achil]=i;
        arr[i]^=arr[i/2];
        arr[i/2]^=arr[i];
        arr[i]^=arr[i/2];
        heapify_up(i/2);
    }
}
int get_max(){
    return a[1];
}
void update(int i, int val=n){
    int v=heap[i];
    a[v]-=val;
    heapify_down(v);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>n;
    a.assign(n+1,0);
    heap.assign(n+1,0);
    arr.assign(n+1,0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]+=i;
        arr[i]=heap[i]=i;
    }
    for(int i=n/2;i>0;i--)
        heapify_down(i);
    for(int i=n;i>0;i--){
        cout<<get_max()+(n-i);
        if(i>1)cout<<' ';
        update(i);
    }
    cout<<'\n';
}