In this HackerEarth Utkarsh and Party Row House problem solution In the college where Utkarsh studies, all the students live in N Row Houses. The colony containing the Row Houses is a straight line = x axis. Ith Row House is located at x = i and Ai students live in it.

Every week the students of some Row House at x=K organize a party and invite all the students living in Row Houses from x=L to x=R.

Utkarsh wants you to handle Q events. An event can be one of the following 2 types.
  1. K L R: Row House at x=K organizes a party and invites all students living in Row House from x=L to x=R. Tell the sum of distance traveled by all the guests.
  2. If a guest is at x=i and party is at x=j then distance travelled by him alone is |i - j|.
  3. K S: S new students are admitted into the college and all of them start to live in Row House at x=K

HackerEarth Utkarsh and Party Row House problem solution


HackerEarth Utkarsh and Party Row House problem solution.

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define fre     freopen("0.in","r",stdin);freopen("0.out","w",stdout)
#define abs(x) ((x)>0?(x):-(x))
#define MOD 1000000007
#define lld signed long long int
#define pii pair<int,int>
#define scan(x) scanf("%d",&x)
#define print(x) printf("%d\n",x)
#define scanll(x) scanf("%lld",&x)
#define printll(x) printf("%lld\n",x)
vector<int> G[2*100000+5];
#define MAX_N 100000
lld t1[MAX_N+5];
lld t2[MAX_N+5];
lld read(lld *bit,int idx){
    lld sum = 0;
    if(idx==0)
        return 0;
    while (idx > 0){
        sum += bit[idx];
        idx -= (idx & -idx);
    }
    return sum;
}
void update(lld *bit,int idx ,lld val){
    while (idx <= MAX_N){
        bit[idx] += val;
        idx += (idx & -idx);
    }
}
lld rangeQuery(lld *bit,int i,int j){
    return read(bit,j) - read(bit,i-1);
}
int main(){
    int N,Q,L,R,K;
    lld S,x;
    cin>>N>>Q;
    for(int i=1;i<=N;++i){
        scanll(x);
        update(t1,i,x);
        update(t2,i,i*x);
    }
    while(Q--){
        int C;
        scan(C);
        if(C==1){
            scan(K);
            scan(L);
            scan(R);
            lld ans = 0;
            if(K<=L){
                ans = rangeQuery(t2,L,R) - rangeQuery(t1,L,R)*K;
            }
            else if(K<=R){
                ans = rangeQuery(t2,K,R) - rangeQuery(t1,K,R)*K
                    + rangeQuery(t1,L,K)*K - rangeQuery(t2,L,K);
            }
            else{
                ans = rangeQuery(t1,L,R)*K - rangeQuery(t2,L,R);
            }
            printll(ans);
        }
        else{
            scan(K);
            scanll(S);
            update(t1,K,S);
            update(t2,K,K*S);
        }
    }
}

Second solution

#include <iostream>
#include <cstdio>

using namespace std;

int n, q;
const int MAXN = 100100;
long long a[MAXN];
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    for (int it = 1; it <= q; it++) {
        int tp;
        scanf("%d", &tp);
        if (tp == 1) {
            int k, l, r;
            scanf("%d%d%d", &k, &l, &r);
            long long res = 0;
            for (int j = l; j <= r; j++) {
                res += a[j]*abs(j - k);
            }
            printf("%lld\n", res);
        }
        else {
            int wh, s;
            scanf("%d%d", &wh, &s);
            a[wh] += s;
        }

    }
    return 0;
}