In this HackerEarth Shantam and Richness problem solution, Shantam is very rich, even richer than Richie Rich. He is extremely talented in almost everything except one, mathematics. So one day, he pays a visit to a temple (to pray for his upcoming mathematics exams) and decides to donate some amount of money to the poor people ( everyone is poor on a relative scale to Shantam). He orders N people to sit in a linear arrangement and indexes them from 1 to N, to ease the process of donating money.

As with all rich people, their way of doing things is completely eerie and different. Shantam donates his money in M steps, each of his steps being to choose two indices L and R, and an amount of money C and then he donates C currencies to each and every person whose index lies in [L, R]. In other words, he donates C currencies to every index i such L <= i <= R.

Luckily, you too were among the N people selected and somehow you know all the M steps in advance. Figure out the maximum amount of money you can obtain and at what position you should sit to get this maximum amount of money. If multiple positions guarantee the maximum amount of money, output the minimum index out of all these possibilities.


HackerEarth Shantam and Richness problem solution


HackerEarth Shantam and Richness problem solution.

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

#define all(c)    c.begin(),c.end()
#define sz(c)     (int)c.size()
#define clr(c)    c.clear()
#define pb        push_back
#define mp        make_pair

#define cin(x)     scanf("%d",&x)

#define FOR(i,a,b)      for(int i=(int)(a);i<(int)(b);i++)
#define RFOR(i,a,b)     for(int i=(int)(b)-1;i>=(int)(a);i--)

LL startAt[100001];
LL endAt[100001];
LL arr[100001];

int L[100001];
int R[100001];
int C[100001];

void solve()
{
    int n , m;
    cin(n);
    cin(m);
    assert(n >= 1 && n <= 100000);
    assert(m >= 1 && m <= 100000);
    for(int i = 0; i <= 100000; i++)
        L[i] = R[i] = C[i] = 0;
    
    cin(L[0]);
    cin(R[0]);
    cin(C[0]);

    int p , q , s;
    cin(p);
    cin(q);
    cin(s);
    
    assert(L[0] >= 1 && L[0] <= n);
    assert(R[0] >= 1 && R[0] <= n);
    assert(C[0] >= 1 && C[0] <= 1000000);
    assert(p >= 1 && p <= 10000);
    assert(q >= 1 && q <= 10000);
    assert(s >= 1 && s <= 10000);

    for(int i = 1; i < m; i++)
    {
        L[i] = (1LL * L[i-1] * p + R[i-1]) % n + 1;
        R[i] = (1LL * R[i-1] * q + L[i-1]) % n + 1;
        C[i] = (1LL * C[i-1] * s) % (1000000) + 1;
        if(L[i] > R[i])
            swap(L[i] , R[i]);
    }

    for(int i = 0; i <= n; i++) arr[i] = startAt[i] = endAt[i] = 0;
    for(int i = 0; i < m; i++)
    {
        startAt[L[i]] += C[i];
        endAt[R[i]] += C[i];
    }
    LL sum = 0;
    for(int i = 0; i <= n; i++)
    {
        sum += startAt[i];
        arr[i] = sum;
        sum -= endAt[i];
    }   
    int pos = 0;
    for(int i = 1; i <= n; i++)
    {
        if(arr[pos] < arr[i])
            pos = i;
    }
    printf("%d %lld\n", pos , arr[pos]);
}

int main()
{
    int t;
    cin(t);
    assert(t >= 1 && t <= 200);
    while(t--)
    {
        solve();
    }
    return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define pi pair<ll,ll>
#define pii pair<pi,int>
#define f first
#define s second
#define mod 1000000007
#define pb push_back
typedef node* pnode;
struct node{
    int prior,size,val;
    pnode l,r;
};
int sz(pnode t){
    return (t?t->size:0);
}
void upd_sz(pnode t){
    if(t){
        t->size=1+sz(t->l)+sz(t->r);
    }
}
void split(pnode t,pnode &l,pnode &r,int pos,int add=0){
    if(!t){
        l=r=NULL;
        return ;
    }
    int cur_pos=add+sz(t->l);
    if(cur_pos<=pos){
        split(t->r,t->r,r,pos,cur_pos+1),l=t;
    }
    else{
        split(t->l,l,t->l,pos,add),r=t;
    }
    upd_sz(t);
}
void merge(pnode &t,pnode l,pnode r){
    if(!l or !r){
        t=(l?l:r);
        return;
    }
    if(l->prior>r->prior) merge(l->r,l->r,r),t=l;
    else merge(r->l,l,r->l) , t=r;
    upd_sz(t);
}
pnode init(int val){
    pnode ret=(pnode)malloc(sizeof(node));
    ret->prior=rand();
    ret->l = ret->r = NULL;
    ret->val = val;
    return ret;
}
pnode root,A[100011];
int main(){
    root=NULL;
    int cnt=0;
    int tot=0;
    cin >> n;
    while(n--){

    }
}