new idea for add in the range [a,b] ( no segment tree )


                             A. Greg and Array

http://codeforces.com/problemset/problem/295/A



If it is told to add in the range [a,b] with c . we just add array[a]+=c  and array[b+1]-=c;
After that we just need to do cumulative sum. It  will give the final array :)





#include<bits/stdc++.h>

using namespace std;

long long int a[500005],b[500005];
long long int op[500005],k[100005][3];



int main()
{
long long int n,i,j,l,ut,ui,p,q,ad;

cin>>n>>ut>>ui;

for(i=1;i<=n;i++)
cin>>a[i];

for(i=1;i<=ut;i++)
{
 cin>>k[i][0]>>k[i][1]>>k[i][2];
}


for(i=1;i<=n+1;i++)
    op[i]=0;

for(i=1;i<=ui;i++)
{
 cin>>p>>q;
 op[p]++;
 op[q+1]--;
}

for(i=2;i<=ut;i++) op[i]+=op[i-1];

/*for(i=1;i<=n;i++)
    cout<<op[i]<<" ";
     cout<<endl;*/



for(i=1;i<=n+1;i++) b[i]=0;

for(i=1;i<=ut;i++)
{
   b[k[i][0]]+=op[i]*k[i][2];
   b[k[i][1]+1]-=(op[i]*k[i][2]);
}


for(i=2;i<=n;i++)
{
 b[i]+=b[i-1];
 //a[i]+=a[i-1];
}

for(i=1;i<=n;i++)
    a[i]+=b[i];

for(i=1;i<=n;i++)
    cout<<a[i]<<" ";
     cout<<endl;

return 0;
}



Comments

Popular posts from this blog

Getting Started With MEAN App Development with AngularJs , ExpressJs , NodeJs and MongoDB.

B. Dreamoon and WiFi :calculate no. of ways : recursive solution (branch and bound )

A. Dreamoon and Stairs : minimum steps to reach : recursion solution.