Editorial for Alohomora 2021 : Team Rocket

editorial
, , ,
1

Problem Link: CodeChef: Practical coding for everyone
Author: @sharshach
Tester: @regex0754
Difficulty: Medium
PREREQUISTIES: Math, SegmentTree or related concepts

Basic Idea :

Let us assume
SumRight=sum of all values whose X>currentX
SumTop=sum of all values whose Y>currentY

Now when we consider SumRight+sumTop we get the quadrant1 covered twice quadrant 2 and 4 covered once quadrant 3 covered 0 times.

Now reduce the totalSum (till now) you will get quadrant1 one time covered and quadrant3 subtracted once which is our goal

So our solution is sumLeft+sumTop-TotalSum

Now focus on calculating sumLeft

We can use segment tree for this focusing on 2 methods (updating the value) and getting sumRight.

Same way we can do for sumTop using y values in another segment tree

Setter Code

#include<bits/stdc++.h>
using namespace std;
 
class Tree{
    int N;
    unordered_map <int,long long int> data;
    long long int _getSumRight(int index){
        if(index==0)return 0;
        if(index%2==1){
            return data[index]+(__builtin_popcount(index+1)==1?0:_getSumRight(index+1));
        }
        return _getSumRight(index/2);
    }   
    int getNext2Power(int N){
        if(__builtin_popcount(N)==1)return N;
        int ans=1;
        while(N){
            N=N>>1;
            ans=ans<<1;
        }
        return ans;
    }
public:
    Tree(int N){
        this->N=getNext2Power(N);
    }
    void insert(int index,int value){
        index+=N;
        do{
            if(data.find(index) == data.end()){
                data[index]=value;
            }
            else{
                data[index]+=value;
            }
        }while(index/=2);
    }
    long long int getSumRight(int index){
        return _getSumRight(index+N);
    }
};
class solve{
    Tree *X,*Y;
    long long int totalSum=0;
public:
    solve(int N){
        X=new Tree(N);
        Y=new Tree(N);
    }
    void insert(int x,int y,int value){
        X->insert(x+500000,value);
        Y->insert(y+500000,value);
        totalSum+=value;
    }
    long long int getSolution(int x,int y){
        x+=500000;
        y+=500000;
        return X->getSumRight(x)+0ll+Y->getSumRight(y)-totalSum;
    }
};
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t,n,x,y,v;
    cin>>t;
    while(t--){
        cin>>n;
        solve s(1000001);
        while(n--){
            cin>>x>>y>>v;
            s.insert(x,y,v);
            cout<<s.getSolution(x,y)<<endl;
        }
    }
    return 0;
}

Tester Code

#include<bits/stdc++.h>
#define ll long long int
#define here cout<<"here\n"
#define pb push_back
#define mp make_pair
#define file freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); 
#define XLR8 ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
 
const ll mod = 1e9+7;
 
const int MAX = 1000005;
 
vector<ll>arrx,arry,stx,sty;
 
 
 
ll query(ll si, ll ss, ll se,ll qs, ll qe, vector<ll>&st)
{
 
    if( qs>se || qe<ss )   
    {
        return 0;
    }
 
    if(ss>=qs && se<=qe) 
    {
        return st[si];  
    }
 
    ll mid = (ss+se)/2;
    ll l = query(2*si, ss, mid, qs, qe,st);
    ll r = query(2*si+1, mid+1, se, qs, qe,st);
 
    return l+r;
}
 
 
void update(ll si, ll ss, ll se, ll qi, vector<ll>&arr, vector<ll>&st)
{
    if(ss==se)
    {
        st[si] = arr[qi];
        return;
    }
    ll mid = (ss+se)/2;
    if(qi<=mid)
        update(2*si,ss,mid,qi,arr,st);
    else
        update(2*si+1,mid+1,se,qi,arr,st);
 
    st[si] = st[2*si] + st[2*si+1];
}
 
 
 
int main()
{
 
    #ifndef ONLINE_JUDGE
        file;
    #endif
 
    XLR8;
 
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        arrx.assign(MAX,0);
        stx.assign(4*MAX,0);
        arry.assign(MAX,0);
        sty.assign(4*MAX,0);
        ll i,j,k,l;
        // here;
        for(i=0;i<n;i++)
        {
            cin>>k>>j>>l;
            k+=5e5;
            j+=5e5;
            arrx[k] += l;
            arry[j] += l;
 
            update(1,1,1e6,k,arrx,stx);
            update(1,1,1e6,j,arry,sty);
 
            cout<<query(1,1,1e6,j,1e6,sty)-query(1,1,1e6,1,k-1,stx)<<endl;
        }
        // here;
 
    }
 
 
 
    return 0;
}